Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | horse.in, horse.out | Sursă | Lot Juniori 2009 - Baraj 2 |
| Autor | Zoltan Szabo | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Horse
Se consideră o tablă de şah cu n linii şi n coloane, şi n=4k+1. Liniile acestei table sunt numerotate de sus în jos începând cu linia 1, iar coloanele sunt numerotate de la stânga la dreapta începând cu 1. În fiecare dintre câmpurile acestei table se scrie câte un număr natural din mulţimea {1, 2, …, n2} după următoarele reguli:
a) se porneşte din colţul aflat în poziţia stânga sus al tablei şi se avansează utilizând săritura calului
b) se merge orizontal către dreapta şi în continuare, pe chenarul format din primele două linii, primele două coloane, ultimele două linii şi ultimele două coloane, în sensul acelor de ceasornic;
c) se efectuează mai multe tururi ale tablei, până ce se umple întregul chenar, fără să se sară de două ori în aceeaşi căsuţă, fără să se sară în afara acestui chenar şi fără să rămână vreun câmp liber;
d) din poziţia finală în care s-a ajuns, trebuie să fie posibilă săritura în colţul din stânga sus al pătratului rămas neacoperit;
e) se continuă deplasarea în interiorul pătratului rămas neacoperit, folosind regulile a), b), c), d) până ce se ajunge la pătratul interior de latură 1 care va conţine valoarea n2.
Amintim că o săritură a calului constă într-o deplasare de două căsuţe pe orizontală urmată de o deplasare de o căsuţă pe verticală sau într-o deplasare de două căsuţe pe verticală urmată de o deplasare de o căsuţă pe orizontală. Calul din figura următoare poate ajunge printr-o săritură în oricare dintre cele 8 poziţii haşurate:
De exemplu, pentru n=5, după un tur al tablei, se obţine următoarea acoperire parţială:
Iar după al doilea tur, se obţine acoperirea parţială:
Pentru n=9, acoperirea se realizează astfel:
Umplere completă: Umplerea succesivă a chenarelor:
Date de intrare
Fişierul de intrare horse.in ...
Date de ieşire
În fişierul de ieşire horse.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| horse.in | horse.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
