== include(page="template/taskheader" task_id="sudoku1") ==
Numim tablou Sudoku o matrice cu nxn elemente ce conține doar cifrele 1, 2 și 3 astfel încât în fiecare pătrat format din 2 x 2 elemente alăturate să existe toate cele 3 cifre și oricare două elemente alăturate pe linie sau pe coloană să fie distincte. Fiecărui tablou Sudoku i se asociază un număr obținut prin scrierea cifrelor în ordine, începând cu prima linie.
Numim tablou Sudoku o matrice cu $n x n$ elemente ce conține doar cifrele [$1$], $2$ și $3$ astfel încât în fiecare pătrat format din $2 x 2$ elemente alăturate să existe toate cele $3$ cifre și oricare două elemente alăturate pe linie sau pe coloană să fie distincte. Fiecărui tablou Sudoku i se asociază un număr obținut prin scrierea cifrelor în ordine, începând cu prima linie.
!>problema/sudoku1?s1.jpg!
De exemplu, tabloul Sudoku din imaginea alăturată are asociat numărul: 2132132132213211321321321.
De exemplu, tabloul Sudoku din imaginea alăturată are asociat numărul: 2132132132213211321321321.
Se definește șirul $S(n)$ ca fiind un șir ordonat, format din toate tablourile Sudoku cu $n x n$ elemente, ${s[~1~], s[~2~], s[~3~], …}$. Pentru orice pereche $(s[~i~], s[~j~])$ din $S(n)$ cu $i < j$, numărul asociat tabloului Sudoku s[~i~] este strict mai mic decât numărul asociat tabloului Sudoku s[~j~].
Se definește șirul S(n) ca fiind un șir ordonat, format din toate tablourile Sudoku cu nxn elemente, {s1,s2,s3,…}. Pentru orice pereche (si,sj) din S(n) cu i<j, numărul asociat tabloului Sudoku si este strict mai mic decât numărul asociat tabloului Sudoku sj.
Pentru $n = 2$, șirul $S(2)$ conține, în ordine, tablourile Sudoku:
Pentru n=2, șirul S(2) conține, în ordine, tablourile Sudoku:
!problema/sudoku1?s2.jpg!
h2. Cerinta
h2. Cerința
Date fiind două numere naturale n și k să se determine:
a) numărul tablourilor Sudoku din șirul S(n);
b) tabloul Sudoku aflat pe poziția k în șirul S(n).
Date fiind două numere naturale $n$ și $k$ să se determine:
* $a)$ numărul tablourilor Sudoku din șirul $S(n)$;
* $b)$ tabloul Sudoku aflat pe poziția $k$ în șirul $S(n)$.
h2. Date de intrare
Fișierul sudoku.in conține pe prima sa linie două numere naturale n și k separate prin câte un spațiu.
Fișierul $sudoku1.in$ conține pe prima sa linie două numere naturale $n$ și $k$ separate prin câte un spațiu.
h2. Date de ieșire
Fișierul de ieșire sudoku.out va conține:
• pe prima linie un număr natural ce reprezintă numărul tablourilor Sudoku din șirul S(n);
• pe următoarele n linii se găsesc câte n cifre, separate prin câte un spațiu, ce reprezintă, în ordine, liniile tabloului Sudoku aflat pe poziția k în șirul S(n).
Fișierul de ieșire $sudoku1.out$ va conține:
* pe prima linie un număr natural ce reprezintă numărul tablourilor Sudoku din șirul $S(n)$;
* pe următoarele $n$ linii se găsesc câte $n$ cifre, separate prin câte un spațiu, ce reprezintă, în ordine, liniile tabloului Sudoku aflat pe poziția $k$ în șirul $S(n)$.
h2. Restricții
• 2 n 32;
• 1 k <1019;
• Pentru rezolvarea corectă a cerinței a) se acordă 20% din punctaj, iar pentru rezolvarea corectă cerinței b) se acordă 80% din punctaj.
• Acordarea punctajului pentru a doua cerință se face numai dacă în fișierul de ieșire există un răspuns pentru prima cerință, indiferent de corectitudinea acestuia.
* $2 ≤ n ≤ 32$;
* $1 ≤ k < 10[^19^]$;
* Pentru rezolvarea corectă a cerinței $a)$ se acordă $20%$ din punctaj, iar pentru rezolvarea corectă cerinței $b)$ se acordă $80%$ din punctaj.
* Acordarea punctajului pentru a doua cerință se face numai dacă în fișierul de ieșire există un răspuns pentru prima cerință, indiferent de corectitudinea acestuia.
h2. Exemplu
table(example).
table(example).
|_. sudoku1.in |_. sudoku1.out |
| 2 6
| 12
