Cu calu' la JBOI

cclj

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

Neînfricatul $K0Kalaru 47$ a dat din nou lovitura. Acesta s-a calificat la renumita competiţie internaţională $JBOI$. Întrucât $K0Kalaru 47$ a investit foarte mult în pregătirea sa de adevărat olimpic, acesta nu mai are cu ce să vină la competiţie, prin urmare a împrumutat un cal de la vecinul său, Sorinel. $K0Kalaru 47$ nu este bun la geografie, aşa că este de datoria voastră să-l ajutaţi să ajungă. Dar, ghiciţi ce! el a devenit atât de bun în ultimul an încât dacă acesta ajunge la competiţie o să ia $MAXIM$ (şi evident primul loc). Acest lucru nu trebuie lăsat să se întâmple (doar echipa României are voie să ia $MAXIM$), aşa că voi trebuie să-i daţi $K0Kalarului 47$ un traseu cât mai lung ca să nu reuşească să ajungă la timp la $JBOI$. Din nefericire, pe cât de praf este el la geografie, pe atât de bună memorie are. Aşa că voi trebuie să-i daţi un traseu cât mai lung şi care nu trece printr-un loc de mai multe ori (altfel acesta o să se prindă că l-aţi măsluit).
Suprafaţa pe care poate călători $K0Kalaru 47$ (acesta stă cam prost cu actele de identitate şi nu are voie să părăsească regiunea est-europeană) are formă unei table $NxM$. Calul $K0Kalarului 47$ poate să se deplaseze doar în formă de $L$ (exact cum o fac toţi caii de pe lumea asta). Scopul vostru este să generaţi o serie de mutări de cal cu cardinal maxim. Puteţi începe şi termina oriunde, dar la punctare se va ţine cont dacă s-a început şi/sau terminat în colţuri.

Neinfricatul Sorinel a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la JBOI. Pentru ca Sorinel 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. Sorinel nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar ghiciti ce, Sorinel a devenit atat de bun in ultimul ana incat daca acesta ajunge la competitie o sa ia $MAXIM$ si evident primul loc. Acest lucru nu se poate intampla (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati lui Sorinel un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la JBOI. Din nefericire, la cat de praf este Sorinel la geografie, 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 salatori Sorinel (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 de oriunde.

h2. Date de intrare

h2. Date de intrare

Fişierul de intrare $cclj.în$ conţine un număr $t$ care semnfică numărul de teste. Pe următoarele $t$ linii se află câte două numere $N$ şi $M$ despărţite printr-un spaţiu, reprezentând dimensiunea tablei.

Fişierul de intrare $cclj.in$ contine doua numere $N$ si $M$ despartite printr-un spatiu.

h2. Date de ieşire

h2. Date de ieşire

Fişierul de ieşire $cclj.out$ conţine răspunsul pentru fiecare test. Pe prima linie a fiecărui test se află numărul $K$ ce semnifică numărul de căsuţe prin care $K0Kalaru 47$ o să treacă. Pe următoarele $N$ linii se află câte $M$ numere ce reprezintă o matrice $A$ care codifică cele $K$ căsuţe prin care se trece în felul următor: drumul $K0Kalarului 47$ începe în căsuţa în care $A[i][j]$ este $1$, continuă unde este $2$, etc, termindanu-se unde se află valoarea $K$. În caz că printr-o căsuţa nu se trece, trebuie să afişaţi $0$. În matricea $A$ nu trebui să existe vreun număr în afară de $0$ care apare de mai multe ori. De asemenea toate numerele trebuie să fie întregi în intervalul $[0, K]$.
 
h2. Restricţii
 
* $1 ≤ t ≤ 10$
* $8 ≤ N, M ≤ 500$
 
* **Full Feedback!**
* **Subtask 1 (20 puncte):** $N, M ≤ 20$
* **Subtask 2 (20 puncte):** $N = M, N$ dă restul $1$ la împărţirea cu $4$
* **Subtask 3 (20 puncte):** $N = M, N$ este o putere de $2$
* **Subtask 4 (40 puncte):** Restricţii iniţiale
 
h2. Punctaj
 
Punctajul obţinut pe un test este: <tex> punctaj = (\frac{K}{NrMax})^{2}*Pointspertest </tex>, unde $K$ este cel de mai sus, $NrMax$ este numărul maxim de căsuţe prin care se poate trece în condiţiile de mai sus, iar $Pointspertest$ reprezintă câte puncte valorează testul ( $70%$ din punctajul maxim acordat testului dacă niciunul dintre capete nu este într-un colţ, $85%$ pentru un capăt şi $100%$ pentru ambele) .
Punctajul final este suma punctajelor obţinute la fiecare test.
 
h2. Exemplu
 
table(example). |_. cclj.în |_. cclj.out |
| 2
10 10
8 9
|7
1 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 7 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
16
1 0 9 0 7 0 0 0 0
0 0 2 0 0 0 0 0 0
3 10 0 8 0 6 0 0 0
0 0 0 5 0 0 0 0 0
11 4 0 0 0 0 0 0 0
0 0 12 0 0 0 0 15 0
0 0 0 0 13 0 0 0 0
0 0 0 0 0 0 14 0 16
|

Pe prima linie a fisierului de iesire $cclj.out$ se afla numarul $Nr$ ce semnifica numarul de casute prin care Sorinel o sa treaca. Pe urmatoarele $Nr$ linii se afla cate doua numere $x$ si $y$ ce semnifica casutele prin care Sorinel o sa treaca. Fiecare casuta tebuie sa apara cel mult o data.
 
h2. Restricţii
 
* 10<=N, M<=1000

h3. Explicaţie

h2. Exemplu
 
table(example). |_. cclj.in |_. cclj.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

**Atentie!**: Exemplul nu obtine 10 puncte si nici drumurile nu au lungime optima.

h3. Explicaţie

În exemplu, presupunând că ar valora 10 puncte, fiecăruia din teste îi vor fi atrbuite câte 5 puncte. În acest caz la primul test se va pleca din punctajul de 0.85 * 5 = 4.25 puncte, în timp ce la al doilea test se va pleca din punctajul de 1.0 * 5 = 5 puncte.

...

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

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