Fişierul intrare/ieşire:	cclj.in, cclj.out	Sursă	Junior Challenge 2015
Autor	Costin Oncescu	Adăugată de	JuniorChallenge2016 •JuniorChallenge2015
Timp execuţie pe test	1 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Cu calu' la JBOI

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.

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.

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

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

Punctaj

Punctajul obţinut pe un test este: , 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.

Exemplu

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.

Cum se trimit solutii?