Diferente pentru problema/tris intre reviziile #1 si #4

Diferente intre titluri:

tris
Tris

Diferente intre continut:

== include(page="template/taskheader" task_id="tris") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $tris.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $tris.out$ ...
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.
h2. Restricţii
h2. Evaluare
* $... ≤ ... ≤ ...$
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 |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
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:
h3. Explicaţie
* 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.
...
!problema/tris?bad.png!
== include(page="template/taskfooter" task_id="tris") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.