== include(page="template/taskheader" task_id="tris") ==
Ninel, fratele mai mic al lui Gigel, a primit de ziua lui un joc tetris în care toate piesele sunt formate din maxim 3 pătrăţele. Există 4 tipuri de astfel de piese care, luând în considerare rotirile pieselor, se pot plasa pe un grid în 9 moduri distincte:
!problema/tris?figuri.png!
Jocul conţine din fiecare tip de piesă cel puţin 2 şi cel mult 100 de bucăţi. El doreşte să plaseze toate piesele astfel încât acestea să formeze un ciclu, adică orice pătrăţel să aibă exact doi vecini pe cele patru direcţii (sus, jos, dreapta, stânga) şi zona interioară ciclului să fie conexă pe cele patru direcţii. O mulţime de pătrăţele se consideră zonă conexă dacă din oricare pătrăţel din mulţime se poate ajunge în oricare alt pătrăţel trecând doar prin pătrăţele din mulţime pe cele patru direcţii.
h2. Cerinţă
Cunoscând numărul de piese din fiecare tip, ajutaţi-l pe Ninel să rezolve problema.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul $tris.in$ conţine pe o singură linie 4 numere naturale a b c d, separate prin câte un spaţiu, reprezentând numărul de piese de tipul 1x1, 2x1, 3x1 respectiv L în această ordine.
Fişierul de intrare $tris.in$ ...
h2. Date de ieşire
Fişierul $tris.out$ va conţine pe prima linie două numere n şi m, reprezentând dimensiunile matricei-soluţie.
Pe următoarele n linii se vor afla câte m numere naturale din mulţimea {0,1,…, a+b+c+d}, fiecare element semnificând:
* 0 – dacă pe poziţia respectivă nu se găseşte niciun element;
* i – dacă pe poziţia respectivă este plasată una din cele a+b+c+d piese, identificată cu numărul i.
Piesele pot fi numerotate în orice ordine cu numere de la 1 la a+b+c+d, cu condiţia ca acestea să aibă numere distincte.
În fişierul de ieşire $tris.out$ ...
h2. Evaluare
h2. Restricţii
O soluţie se consideră validă dacă şi numai dacă se respectă următoarele condiţii:
* dimensiunile matricei sunt cel mult egale cu 800x800;
* fiecare celulă ocupată de o piesă are exact 2 vecini;
* zona ocupată de piese formează un ciclu;
* zona interioară ciclului este conexă pe cele patru direcţii.
h2. Restricţii şi precizări
* $pentru datele de intrare problema întotdeauna are soluţie;$
* $pentru 30 de puncte 10 ≤ a, b, c, d ≤ 100;$
* $pentru 50 de puncte 5 ≤ a, b, c, d ≤ 100;$
* $pentru 80 de puncte 3 ≤ a, b, c, d ≤ 100;$
* $pentru 100 de puncte 2 ≤ a, b, c, d ≤ 100;$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. tris.in |_. tris.out |_. Explicaţie |
| 3 4 3 4
| 11 6
0 1 2 4 4 4
1 1 0 0 0 3
8 0 0 0 3 3
8 0 0 0 9 0
8 0 0 0 9 9
10 0 0 0 0 13
10 0 0 0 0 11
12 0 0 0 0 11
12 0 0 0 0 14
6 0 0 0 0 7
6 5 5 5 7 7
| Avem 3 piese de tip 1x1
Avem 4 piese de tip 2x1
Avem 3 piese de tip 3x1
Avem 4 piese de tip L
Matricea-soluţie este formată
din 11 linii şi 6 coloane:
!problema/tris?exemplu.png!
|
h2. Observaţie:
Următorea matrice nu formează soluţie din multiple motive:
table(example). |_. tris.in |_. tris.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
* există pătrăţele care nu au exact doi vecini (vezi piesele 6, 9, 13 şi respectiv 15);
* zona interioară ciclului nu este conexă pe cele patru direcţii. Există două zone interioare conexe cu 3 pătrăţele, respectiv 13 pătrăţele.
h3. Explicaţie
!problema/tris?bad.png!
...
== include(page="template/taskfooter" task_id="tris") ==
