Fişierul intrare/ieşire:sudoku1.in, sudoku1.outSursăONI 2013 clasa a 8-a
AutorCristina SichimAdăugată detudorcomanTudor Coman tudorcoman
Timp execuţie pe test0.3 secLimită de memorie40960 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Sudoku1 (clasa a 8-a)

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 × 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 n x n elemente, , 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ţ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 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.

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

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.

Exemplu

sudoku1.insudoku1.out
2 6
12
2 1
3 2

Explicaţie

Şirul S(2) conţine 12 tablouri Sudoku, pe poziţia 6 în şir aflându-se tabloul:
2 1
3 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici