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.
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 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:
Cerinţă
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 de intrare
Fişierul sudoku1.in conţine pe prima sa linie două numere naturale n şi k separate prin câte un spaţiu.
Date de ieşire
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).
Restricţii
• 2 ≤ n ≤ 32
• 1 ≤ k <1019
Exemple
sudoku1.in
sudoku1.out
Explicaţii
2 6
12
2 1
3 2
Şirul S(2) conţine 12 tablouri Sudoku, pe poziţia 6 în şir aflându-se tabloul:
2 1
3 2
