Revizia anterioară Revizia următoare
| 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
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 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 si termina oriunde, dar la punctare se va tine cont daca s-a inceput si/sau terminat din colturi.
Date de intrare
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.
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].
Restricţii
- 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 4 (40 puncte): Restrictii initiale
Punctaj
Punctajul obtinut pe un test este: 
, 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.
Exemplu
| 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 6 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*/ |
Explicaţie
...
