Fișierul intrare/ieșire	zana.in, zana.out	Sursă	Olimpiada pe Sector 2010, Clasa a 10-a
Autor	Carmen Mincă	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	1

Vezi soluțiile trimise | Statistici

Zâna (clasa a 10-a)

Castelul Zânei Spiridușilor este construit pe o suprafață de teren dreptunghiulară și are N * M camere identice, de formă pătratică, dispuse câte M pe direcția Ox și câte N pe direcția Oy ca în desenul alăturat în care N = 3 și M = 6. Din fiecare cameră se poate intra în orice cameră învecinată, cameră care are un perete comun cu aceasta. Fiecare cameră este identificată prin coordonatele sale, ca în figură.
În castel trăiesc k spiriduși împreună cu Zâna lor. Fiind în curând aniversarea zilei de naștere a Zânei, fiecare spiriduș a pregătit câte un cadou pe care îl ascunde, nevăzut de ceilalți, într-una din camerele castelului. Tradiția acestei sărbători impune următoarele reguli:

• În căutarea cadourilor, Zâna pornește din camera de coordonate (1, 1). Ea se deplasează prin camerele castelului cât timp în aceste camere nu se află niciun cadou.
• Căutarea se încheie în momentul în care Zâna intră într-o cameră în care se află cel puțin un cadou. Zâna va primi toate cadourile aflate în această cameră iar restul cadourilor din celelalte camere vor dispărea.

Cerință

Scrieți un program care să citească din fișierul zana.in numerele naturale N, M, K și cele K perechi de numere naturale reprezentând coordonatele camerelor în care spiridușii au ascuns cadourile, și care să determine:

• numărul maxim X de cadouri pe care le poate primi Zâna în urma respectării regulilor;
• numărul Y de camere în care poate ajunge Zâna respectând regulile, camere ce conțin fiecare câte X cadouri.

Date de intrare

Fișierul zana.in conține pe prima linie cele trei numere naturale: N, M, K, separate prin câte un spațiu. Pe fiecare din următoarele K linii, câte una pentru fiecare spiriduș, sunt scrise câte două numere naturale: I, J, separate printr-un spațiu, reprezentând coordonatele camerei în care spiridușul curent a ascuns cadoul.

Date de ieșire

Fișierul zana.out va conține două linii. Pe prima linie se va scrie numărul natural X reprezentând numărul maxim de cadouri pe care le poate primi Zâna conform tradiției. Pe cea de-a doua linie se va scrie numărul natural Y, reprezentând numărul camerelor în care poate ajunge Zâna și care conțin fiecare câte X cadouri.

Restricții

• K, M, N, I, J sunt numere naturale nenule
• 2 ≤ N, M ≤ 100
• 10 ≤ K ≤ 510
• 1 ≤ I ≤ N
• 1 ≤ J ≤ M
• Se garanteaza ca nu exista cadouri in casuta (1, 1)

Exemplu

Explicație

Zâna pornește căutarea începând din camera de coordonate (1, 1). Camera cu cele mai multe cadouri (3) are coordonatele (1, 4), însă zâna nu poate ajunge în acestă cameră, deoarece pentru a ajunge în acesta ea trebuie să treacă prin una din camerele de coordonate (1, 3), (2, 4), (2, 5) în care se află cadouri. Conform tradiției, căutarea se va încheia în una dintre aceste camere. Astfel zâna poate parcurge camerele (1, 1), (1, 2), (1, 3) sau (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), etc pentru a ajunge într-una din cele Y = 2 camere cu un număr X = 2 maxim de cadouri.