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 K0Kalaru 47 a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la JBOI. Pentru ca 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 se poate intampla (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, la cat de praf este el 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 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 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 un numar $t$ care semnfica numarul de teste. Pe urmatoarele $t$ linii se afla cate doua numere $N$ si $M$ despartite printr-un spatiu, reprezentand dimensiunea tablei.

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

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $Nr$ ce semnifica numarul de casute prin care K0Kalaru 47 o sa treaca. Pe urmatoarele $Nr$ linii se afla cate doua numere $x$ si $y$ ce reprezinta sirul de casute prin care K0Kalaru 47 trece in ordinea in care apar in fisierul de iesire. Fiecare casuta trebuie sa apara cel mult o data in cadrul unui test.
 
h2. Restricţii
 
* 1 ≤ t ≤ 10
* 8 ≤ N, M ≤ 1000
 
* **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})^{1.5}*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.
Punctajul final este suma punctajelor obtinute la fiecare test.
 
h2. Exemplu
 
table(example). |_. cclj.in |_. cclj.out |
| 1
10 10
| 0 0 0 0 0 0 0 0 0 0
0 0 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 5 0 0 0
0 0 0 0 0 0 0 0 9 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
/*6
2 3
3 5
2 7
3 9
5 8
7 9*/

|

h3. Explicaţie

h3. Explicaţie

**Atentie!**: Exemplul nu obtine 10 puncte si nici drumurile nu au lungime optima.
 
Î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") ==