cclj

Cu calu' la JBOI

== include(page="template/taskheader" task_id="cclj") ==

Neinfricatul K0Kalaru 47 a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la JBOI. Intrucat K0Kalaru 47 a investit foarte mult in pregatirea sa de adevarat olimpic, acesta nu mai are cu ce sa vina la competitie, asa ca a imprumutat un cal de la vecinul sau. K0Kalaru 47 nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar ghiciti ce! El a devenit atat de bun in ultimul an incat daca acesta ajunge la competitie o sa ia $MAXIM$ si evident primul loc. Acest lucru nu trebuie lasat sa se intample (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati K0Kalarului 47 un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la JBOI. Din nefericire, pe cat de praf este el la geografie, pe atat de buna memorie are. Asa ca voi trebuie sa-i dati un traseu cat mai lung si care nu trece printr-un loc de mai multe ori (altfel acesta o sa se prinda ca l-ati masluit).
Suprafata pe care poate calatori K0Kalaru 47 (acesta sta cam prost cu actele de identitate si nu are voie sa paraseasca regiunea Est-Europeana) are forma unei table N*M. Calul lui Sorinel poate sa se deplaseze doar in forma de L (exact cum o fac toti caii de pe lumea asta). Scopul vostru este sa generati o serie de mutari de cal cu cardinal maxim. Puteti incepe si termina oriunde, dar la punctare se va tine cont daca s-a inceput si/sau terminat din colturi.

Neinfricatul $K0Kalaru 47$ a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la $JBOI$. Intrucat $K0Kalaru 47$ a investit foarte mult in pregatirea sa de adevarat olimpic, acesta nu mai are cu ce sa vina la competitie, asa ca a imprumutat un cal de la vecinul sau. $K0Kalaru 47$ nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar ghiciti ce! El a devenit atat de bun in ultimul an incat daca acesta ajunge la competitie o sa ia $MAXIM$ si evident primul loc. Acest lucru nu trebuie lasat sa se intample (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati $K0Kalarului 47$ un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la $JBOI$. Din nefericire, pe cat de praf este el la geografie, pe atat de buna memorie are. Asa ca voi trebuie sa-i dati un traseu cat mai lung si care nu trece printr-un loc de mai multe ori (altfel acesta o sa se prinda ca l-ati masluit).
Suprafata pe care poate calatori $K0Kalaru 47$ (acesta sta cam prost cu actele de identitate si nu are voie sa paraseasca regiunea Est-Europeana) are forma unei table $N*M$. Calul lui Sorinel poate sa se deplaseze doar in forma de $L$ (exact cum o fac toti caii de pe lumea asta). Scopul vostru este sa generati o serie de mutari de cal cu cardinal maxim. Puteti incepe si termina oriunde, dar la punctare se va tine cont daca s-a inceput si/sau terminat din colturi.

h2. Date de intrare

h2. Date de ieşire

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $K$ ce semnifica numarul de casute prin care K0Kalaru 47 o sa treaca. Pe urmatoarele $N$ linii se afla cate M numere ce reprezinta o matrice A care codifica cele $K$ casute prin care se trece in felul urmator: drumul K0Kalarului 47 incepe in casuta in care A[i][j] este 1, continua unde este 2, etc, termindanu-se unde se afla valoarea K.In caz ca printr-o casuta nu se trece, trebuie sa afisati 0. In matricea A nu trebui sa existe vreun numar in afara de 0 care apare de mai multe ori.De asemenea toate numerele trebuie sa fie intregi in intervalul [0, K].

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $K$ ce semnifica numarul de casute prin care $K0Kalaru 47$ o sa treaca. Pe urmatoarele $N$ linii se afla cate $M$ numere ce reprezinta o matrice $A$ care codifica cele $K$ casute prin care se trece in felul urmator: drumul $K0Kalarului 47$ incepe in casuta in care $A[i][j]$ este $1$, continua unde este $2$, etc, termindanu-se unde se afla valoarea $K$. In caz ca printr-o casuta nu se trece, trebuie sa afisati $0$. In matricea $A$ nu trebui sa existe vreun numar in afara de $0$ care apare de mai multe ori. De asemenea toate numerele trebuie sa fie intregi in intervalul $[0, K]$.

h2. Restricţii

* 1 ≤ t ≤ 10
* 8 ≤ N, M ≤ 500

* $1 ≤ t ≤ 10$
* $8 ≤ N, M ≤ 500$

* **Subtask 1 (20 puncte):** N, M ≤ 20
* **Subtask 2 (20 puncte):** N = M, N da restul 1 la impartirea cu 4
* **Subtask 3 (20 puncte):** N = M, N este o putere de 2

* **Subtask 1 (20 puncte):** $N, M ≤ 20$
* **Subtask 2 (20 puncte):** $N = M, N$ da restul $1$ la impartirea cu $4$
* **Subtask 3 (20 puncte):** $N = M, N$ este o putere de $2$

* **Subtask 4 (40 puncte):** Restrictii initiale
h2. Punctaj

Punctajul obtinut pe un test este: <tex> punctaj = (\frac{Nr}{NrMax})^{2}*Pointspertest </tex>, unde $Nr$ este cel de mai sus, $NrMax$ este numarul maxim de casute prin care se poate trece in conditiile de mai sus, iar $Pointspertest$ rerezinta cate puncte valoreaza testul (7 daca niciunul dintre capete nu este intr-un colt, 8.5 pentru un capat si 10 pentru ambele) .

Punctajul obtinut pe un test este: <tex> punctaj = (\frac{Nr}{NrMax})^{2}*Pointspertest </tex>, unde $Nr$ este cel de mai sus, $NrMax$ este numarul maxim de casute prin care se poate trece in conditiile de mai sus, iar $Pointspertest$ rerezinta cate puncte valoreaza testul ($7$ daca niciunul dintre capete nu este intr-un colt, $8.5$ pentru un capat si $10$ pentru ambele) .

Punctajul final este suma punctajelor obtinute la fiecare test.
h2. Exemplu

0 0 0 0 0 0 0 0 0 0
|

h3. Explicaţie
 
...
 

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