Fișierul intrare/ieșire	treasurehunt.in, treasurehunt.out	Sursă	Nerdvana
Autor	Radu-Bogdan Priboi	Adăugată de	cris priboi radu bogdan • priboiradu
Timp de execuție pe test	0.27 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Treasure Hunt

Gogu urmează să înceapă clasa a 7-a. Pentru a profita de ultimele zile de vacanță în Barcelona, acesta decide să meargă la un Treasure Hunt împreună cu prietenii săi. Acest joc funcționează astfel: Gogu și prietenii săi primesc o serie de indicii care îi ghidează pe aceștia spre o comoară ascunsă. Harta orașului este reprezentată sub forma unei matrice cu N linii și M coloane. Fiecare element reprezintă un cod sub forma de număr întreg, X_i,j (0 ≤ i < N, 0 ≤ j < M), care, după ce este decodificat, indică următoarea poziție în care copii trebuie să meargă.
Decodificarea funcționează astfel: se parcurg cifrele numărului X_i,j de la dreapta la stânga până când se ajunge la un număr mai mare sau egal cu 4, fie el NR, și se înlocuiește cu NR % 4 (restul împărțirii lui NR la 4). Se repetă algoritmul până când se ajunge la un număr strict mai mic ca 4.
De exemplu, dacă numărul este 235, după prima etapă se înlocuiește 5 cu 1 (5 % 4) și rezultă numărul 231, după care se înlocuiește 31 cu 3 (31 % 4). Numărul rezultat, 23 este înlocuit cu 3 (23 % 4). Astfel, codul o să fie E (est) și poziția în care copii vor merge este (i, j+1). Există 4 coduri posibile: 0 reprezintă N (nord), 1 reprezintă V (vest), 2 reprezintă S (sud) și 3 reprezintă E (est).

Cerință

Dată fiind harta orașului, numărul de indicii K care trebuie decodificate pentru ca Gogu și prietenii acestuia să câștige jocul, precum și un “fragment” de hartă, să se determine:
1. Dacă fragmentul de hartă, reprezentat sub formă de matrice cu N₁ linii (1 ≤ N₁ ≤ N) și M₁ coloane (1 ≤ M₁ ≤ M), este sau nu parte din harta orașului. Dacă fragmentul reprezintă o submatrice a hărții orașului, se vor afișa coordonatele colțului stânga-sus al fragmentului în harta orașului;
2. Știind că Gogu și prietenii săi pornesc din centru hărții (fie centru de coordonare [N/2], [M/2], unde [x] reprezintă partea întreagă a lui x), determinați cum se termină jocul. Jocul se poate sfârși în trei moduri:
a. “IESIRE DIN HARTA” – atunci când se ajunge în afara hărții, înainte ca Gogu și prietenii acestuia să decodifice cele K indicii
b. “CICLU” – atunci când aceștia ajung la un indiciu deja decodificat, înainte să decodifice cele K indicii
c. “JOC CASTIGAT” – atunci când ei reușesc să decodifice toate cele K indicii și nu se ajunge la niciunul dintre celelalte două situații anterioare
3. Cum arată harta orașului la finalul jocului, după decodificarea indiciilor;

Date de intrare

Fișierul treasurehunt.in conține pe prima linie un număr natural C, care reprezintă numărul cerinței și poate avea valorile 1, 2 sau 3.
În cazul primei cerințe, linia a doua conține conține patru numere naturale, N, M, N1 și M1, cu semnificația de mai sus. Pe următoarele N linii se vor afla câte M numere naturale, codurile care apar pe harta orașului. Pe următoarele N1 linii se vor afla câte M1 numere naturale, codurile care apar pe fragmentul de hartă.
În cazul celei de-a doua și a treia cerințe, linia a doua conține conține trei numere naturale, N, M și K, cu semnificația de mai sus. Pe următoarele N linii se vor afla câte M numere naturale, codurile care apar pe harta orașului.

Date de ieșire

Fișierul treasurehunt.out conține:

• în cazul primei cerințe, se vor afișa coordonatele colțului stânga-sus al fragmentului în harta orașului, dacă fragmentul reprezintă o submatrice a hărții orașului (dacă exista mai multe răspunsuri posibile, se vor afișa coordonatele cu linia minimă, iar in caz de egalitate, cele cu coloana minimă). În caz contrar, dacă fragmentul nu se regăsește în harta orașului, se va afișa -1;
• în cazul celei de-a doua cerințe, se va afișa pe o singură linie modul în care se finalizează jocul (“JOC CASTIGAT” , “IESIRE DIN HARTA”, “CICLU”);
• în cazul celei de-a treia cerințe, se vor afișa N linii, iar pe fiecare linie M coduri, reprezentând harta orașului, în urma decodificării indiciilor de către Gogu și prietenii acestuia;

Restricții

• pentru prima cerință: 1 ≤ N1 ≤ N ≤ 50; 1 ≤ M1 ≤ M ≤ 50
• pentru a doua și a treia cerință: 1 ≤ N1 ≤ N ≤ 1000; 1 ≤ M1 ≤ M ≤ 1000
• K ≤ N * M
• elementele matricelor sunt numere naturale nenule mai mici sau egale cu 2.000.000.000
• coordonatele elementelor din matrice încep de la 0
• pentru rezolvarea corectă a primei cerințe se acordă 30% de puncte, pentru rezolvarea celei de-a doua cerințe se acordă 30 de puncte, iar pentru rezolvarea celei de-a treia cerințe se acordă 40 de puncte

Exemplu

Explicație

...