Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-09 22:06:25.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:euclid.in, euclid.outSursăSummer Challenge 2007, runda 2
AutorIgor NavernioukAdăugată dedanielpDaniel Pasaila danielp
Timp execuţie pe test1.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Euclid

Euclid era un om destept care stia ca timpul masinilor de calcul avea sa vina intr-o zi. Stia ca oamenii aveau sa organizeze competitii pe aceste masini, asa ca a vrut sa contribuie cu un puzzle.
Fiind data o matrice de m linii si n coloane de intregi pozitivi, sa se gaseasca un dreptunghi de inaltime cel putin h si lungime cel putin w, astfel incat numerele din dreptunghi sa aiba cel mai mare cmmdc dintre toate dreptunghiurile de acest fel.

Date de intrare

Fisierul de intrare va incepe printr-o linie ce contine numarul de teste, T. Fiecare test va incepe printr-o linie ce contine m, n, h si w. Urmeaza m linii a cate n intregi pozitivi, descriind matricea de mai sus.

Date de iesire

Pentru fiecare fisier de iesire, scrieti cate o linie continand "Case #x:", dupa care afisati cel mai mare cmmdc (x reprezinta numarul testului).

Restrictii

  • 1 ≤ T ≤ 20
  • 1 ≤ h ≤ m
  • 1 ≤ m,n ≤ 200
  • numerele din matrice sunt intre 1 si 109

Exemplu

euclid.ineuclid.out
3
2 2 1 1
1 2
3 4
3 3 3 1
1 2 3
4 5 6
7 8 9
2 2 2 2
1000000000 1000000000
1000000000 1000000000
Case #1: 4
Case #2: 3
Case #3: 1000000000

Explicatie

  • pentru primul exemplu, este evident ca dreptunghiul cu cmmdc maxim contine doar patratelul de coordonate (1, 1)
  • pentru al 2-lea exemplu dreptunghiul cu cmmdc maxim este format din ultima coloana a matricii; nu exista alt dreptunghi de dimensiuni mai mari sau egale care sa aiba cmmdc-ul mai mare
  • in cazul ultimului exemplu putem alege intreaga matrice