Diferențe pentru problema/treasurehunt între reviziile #16 si #32

== include(page="template/taskheader" task_id="treasurehunt") ==
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 &le; i < [$N$], 0 &le; 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).

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

h2. 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[~1~]$ linii (1 ≤ $N[~1~]$ ≤ [$N$]) și $M[~1~]$ coloane (1 ≤ $M[~1~]$ ≤ [$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

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;
h2. Date de intrare

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

h2. Exemplu

table(example).
|_. treasurehunt.in |_. treasurehunt.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

table(exampl).
|_. treasurehunt.in |_. treasurehunt.out |_. Explicație |
| 1
6 6 2 3
2 5 4 3 3 2
1 9 5 9 5 9
6 7 3 1 8 7
4 4 2 9 5 9
9 0 1 7 3 1
1 2 3 4 5 6
9 5 9
7 3 1
| 1 1
| Fragmentul de hartă apare de 2 ori în harta orașului. Având coordonata liniei minima, se alege matricea cu colțul din stânga-sus pe poziția (1, 1).
|
|2
5 5 6
2360 8064 8968 6881 3049
2784 5042 4180 4782 7290
6563 2163 5105 1841 2884
6008 2705 2174 3158 4595
2951 7128 8525 2785 1074
|JOC CASTIGAT
|Coordonatele de start sunt (2, 2). După decodificarea numărului 5105 se obține E.
5105 -> 5101 -> 51 -> 3
3 corespunde direcției Est, deci urmatoarea poziție este (2, 3).
1841 -> 181 -> 11 -> 3
Urmează pozițiile (2, 4), (1, 4), (0, 4), (0, 3).
După cele K=6 decodificări se ajunge la finalul jocului.
|
|3
5 5 6
2360 8064 8968 6881 3049
2784 5042 4180 4782 7290
6563 2163 5105 1841 2884
6008 2705 2174 3158 4595
2951 7128 8525 2785 1074
|2360 8064 8968 V V
2784 5042 4180 4782 N
6563 2163 E E N
6008 2705 2174 3158 4595
2951 7128 8525 2785 1074
|

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