Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-06-24 20:07:18.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	domino2.in, domino2.out	Sursă	Lot Sibiu 2011 - Baraj 1 Juniori
Autor	Zoltan Szabo	Adăugată de	Simoiu Robert •SpiderMan
Timp execuţie pe test	0.325 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Domino2

Pentru un n dat avem la dispoziţie un set complet de piese de domino. Set complet înseamnă că avem câte o piesă pentru fiecare pereche posibilă de numere din mulţimea {1, 2 ,..., n}. Numerele de pe o piesă pot fi diferite sau egale. În setul complet fiecare piesă apare o singură dată şi nu avem două piese care conţin aceleaşi numere scrise în altă ordine; piesa |i|j| este aceeaşi cu piesa |j|i|.

De exemplu, dacă n = 3, avem şase piese: |1|1|, |2|2|, |3|3|, |1|2|, |3|1|, |2|3|. În jocul de domino, oricare piesă |i|j| poate fi folosită fie ca |i|j|, şi în acest caz avem în stânga numărul i, iar în dreapta numărul j, fie ca |j|i| şi în acest caz avem în stânga numărul j, iar în dreapta numărul i.

Cu piesele pe care le avem la dispoziţie putem forma un şir, dacă respectăm următoarea regulă: două piese aflate în poziţii alăturate în şir trebuie să conţină prima în dreapta şi a doua în stânga un număr egal. Această regulă o vom numi proprietate “stânga-dreapta”. Excepţie de la această regulă fac prima piesă pentru numărul din stânga şi ultima piesă pentru numărul din dreapta. În acest şir, o piesă nu poate să apară de două ori. Exemple:

şir corect pentu un set complet cu n = 3:
şir corect care nu foloseşte toate piesele ale unui set complet cu n = 3:
şir incorect, cu piese ce nu respectă proprietatea “stânga-dreapta” (piesa a treia şi piesa a patra):
şir incorect, în care o piesă se foloseşte de două ori (piesa a treia şi piesa a cincea):