euclid

Euclid

== include(page="template/taskheader" task_id="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 mult $w$, astfel incat numerele din dreptunghi sa aiba cel mai mare cmmdc dintre toate dreptunghiurile de acest fel.

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.

h2. 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.

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.

h2. 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).

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

h2. Restrictii

* $0 ≤ n &le 20$
* $1 ≤ h &le m$
* $1 ≤ m,n ≤ 200$

* $1 ≤ T ≤ 20$
* $1 ≤ h ≤ m$
* $1 ≤ w ≤ n$
* $1 ≤ m,n ≤ 400$
* numerele din matrice sunt intre $1$ si $10^9^$

h2. Exemplu
table(example). |_. euclid.in |_. euclid.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|
h3. 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

== include(page="template/taskfooter" task_id="euclid") ==

== include(page="template/taskfooter" task_id="euclid") ==
 
 

2043