Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | joc15.in, joc15.out | Sursă | Lot Arad 2011 - Baraj 3 Juniori |
| Autor | Alin Burta | Adăugată de |  Simoiu Robert •SpiderMan |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc15
Atunci când este plictisit, Costel inventează jocuri logice şi încearcă să le rezolve. Într-o zi Costel ia o tablă dreptunghiulară împărţită în M x N pătrăţele identice, asemănătoare unei table de şah, şi aşează pe aceasta cuburi identice astfel încât, pe fiecare pătrat al tablei să se afle cel puţin un cub şi cel mult 10 cuburi suprapuse. Costel determină numărul minim de cuburi aşezate pe o poziţie a tablei, notat cu MIN.
El defineşte noţiunea de mutare astfel: alege patru pătrăţele învecinate, care formează un pătrat compus din 2 × 2 pătrăţele şi ridică toate cuburile de pe aceste poziţii astfel ca, pe fiecare dintre cele patru pătrăţele, să existe un număr de cuburi egal cu MIN. Efortul necesar efectuării mutării este egal cu MAX - MIN, unde MAX reprezintă numărul maxim de cuburi aflat pe unul dintre cele patru pătrăţele alese.
Scopul jocului este acela de a obţine acelaşi număr de cuburi, egal cu valoarea MIN, pe fiecare pătrăţel de pe tablă, efectuând un şir de mutări ce necesită un efort total minim. Efortul total depus pentru rezolvarea jocului este egal suma eforturilor mutărilor efectuate.
Cerinţă
Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie 4 unităţi care au forma următoare:
Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele 8 moduri de a le aşeza.
Date de intrare
Fişierul acoperire.in conţine pe prima linie un număr natural N, cu semnificaţia din enunţ.
Date de ieşire
Fişierul acoperire.out va conţine valoarea -1 pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: N linii cu câte N valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu 1, poziţiile ocupate de a doua piesă aşezată se vor codifica cu 2 etc. Corespunzător colţurilor lipsă se va scrie valoarea 0.
Restricţii
- 6 ≤ N ≤ 20
- Piesele trebuie să fie complet în interiorul zonei
- Zona trebuie acoperită integral
- Două piese nu se pot suprapune complet sau parţial
Exemplu
table(example). |_. acoperire.in |_. acoperire.out |
| 6
| 0 7 2 2 2 0
3 7 2 4 4 4
3 7 7 4 5 5
3 3 6 1 1 5
6 6 6 8 1 5
0 8 8 8 1 0
|
