Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | euclid.in, euclid.out | Sursă | Summer Challenge 2007, runda 2 |
| Autor | Igor Naverniouk | Adăugată de |  Daniel Pasaila •danielp |
| Timp execuţie pe test | 1.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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 ≤ w ≤ n
- 1 ≤ m,n ≤ 400
- numerele din matrice sunt intre 1 si 109
Exemplu
| euclid.in | euclid.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) (coordonatele sunt numerotate de la 0)
- 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
