ŠKOLSKO NATJECANJE 2014. / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

Petar je primijetio da se pod pravokutne prostorije u njegovoj školi sastoji od nekoliko različitih tipova pločica kvadratnog oblika raspoređenih u pravokutnu mrežu koja se sastoji od R redaka i S stupaca.

Petar je za potrebe ovog zadatka pločice istog tipa označio istim slovom engleske abecede, razlikujući mala i velika slova.

Tako slova ‘a’ i ‘A’ označavaju različite tipove pločica.

Jako su mu zanimljivi pravokutnici čiji se rubovi sastoje samo od jedne vrste pločica (bez obzira na to kakve se pločice nalaze u njihovoj unutrašnjosti).

Petar je dugo promatrao pod prostorije i na njemu konačno prebrojao N pravokutnika koji i u svojoj širini i u svojoj visini imaju barem dvije pločice.

Također, izračunao je i najveći broj pločica od kojih se sastoji jedan takav pravokutnik (uključujući i pločice na rubu i unutar njega) te označio taj broj s P.

Kako bi provjerio svoje izračune, sada vas moli da napišete program koji će računati brojeve N i P za opisani pod prostorije.

Ulazni podaci

U prvom redu nalaze se dva prirodna broja R i S (3 ≤ R, S ≤ 30) – broj redaka i stupaca od kojih se sastoji pod prostorije.

U svakom od sljedećih R redova nalazi se niz od točno S znakova.

Svaki je znak veliko ili malo slovo engleske abecede, a označava tip pločice na određenoj lokaciji.

Izlazni podaci

U prvi i jedini redak potrebno je ispisati dva nenegativna cijela broja N i P, koji redom označavaju broj pravokutnika čiji se rub sastoji od istih pločica te najveći broj pločica od kojih se sastoji jedan od tih N pravokutnika.

Ukoliko ne postoji niti jedan takav pravokutnik, potrebno je ispisati dvije nule.

Primjer zadatka

Ulaz

4 4
xaax
bbbb
bcbx
bbbx

Izlaz

1 9

Ulaz

5 4
xxxx
xxxb
xxaa
cbaa
bbaa

Izlaz

8 6

Ulaz

3 3
aac
baa
aad

Izlaz

0 0