Diferențe pentru problema/sudoku1 între reviziile #1 si #9

sudoku1

Sudoku1 (clasa a 8-a)

== include(page="template/taskheader" task_id="sudoku1") ==

Poveste și cerință...

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.
 
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~].
 
Pentru $n = 2$, șirul $S(2)$ conține, în ordine, tablourile Sudoku:
 
!problema/sudoku1?s2.jpg!
 
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)$.

h2. Date de intrare

Fișierul de intrare $sudoku1.in$ ...

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

În fișierul de ieșire $sudoku1.out$ ...

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 &le; 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 |

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

| 2 6
| 12
2 1
3 2

|
h3. Explicație

...

Șirul $S(2)$ conține $12$ tablouri Sudoku, pe poziția $6$ în șir aflându-se tabloul:
$2 1$
$3 2$

== include(page="template/taskfooter" task_id="sudoku1") ==