.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » domino2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
domino2


Timp maxim de execuţie / test:
1.5s
Memorie totala disponibilă / stivă:
64MB / 20MB

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:


Î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 pentru 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)



Cerinţă

Determinaţi dacă pentru un n dat se poate forma un şir cu toate piesele de domino dintr-un set complet.

Date de intrare

Fişierul domino2.in conţine pe prima linie o singură valoare naturală n cu semnificaţia de mai sus.

Date de ieşire

Fişierul domino2.out va conţine pe fiecare linie cele două numere aflate pe câte o piesă din şirul cerut separate prin spaţiu. Prima linie va conţine numerele primei piese, a doua linie va conţine numerele de pe a doua piesă, etc. Numerele unei piese vor fi astfel scrise încât să respecte proprietatea “stânga-dreapta”.
Dacă nu există soluţie, pe prima linie a fişierului se afişează valoarea -1.

Restricţii

2 ≤ n ≤ 1500
• Pot exista mai multe soluţii, se acceptă orice soluţie corectă.

Exemple

domino2.indomino2.out
3 1 1 1 2 2 2 2 3 3 3 3 1

autor: Prof. Zoltan Szabo
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la LOT SB 2011: cifre4, grad2, risipa, liste, pixy, neconex, testament, enigma, asfalt1, intervale, lant1, lcdr, jocs, jb
De acelaşi autor: balanta, bonuri, cub, magic, magic2, munte, euclid, banda, biliard, fractie1, fotbal, arctir, orientare, rege, fibo1, piatra, war, aritm, ssmax, sirmax, ikebana, punctfix, lant1, parc1, cubulete, biperm, triunghi6, stiva1
Despre structura repetitiva: cifre1, super, schimb, jeton, descfib, taxe, romane, mobile, cuburi3, tzigla, morse, powerpuff, multimi, ucif, tabel, ocr, numere7, cifre2, piramida, vraji, reforma, cartonas, cabina, case, desen2, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, paranteze, tort, copaci1, ogorul, puncte3, efort, muzeu, smith, biliard, palc, prod3, fazanr, cadouri, bursa, meteo, prodmax, zar, tren4, lego, maraton1, cluburi, domino1, jump, alo, cifra1, case1, brazi, greiere, divizori, pitag, porumb, secv9, divk, rachete, pin, sumacifre, aritm, psp, triplu, triunghi3, cmmdcsecv, ssmax, ape, furnici1, acoperire1, ore, pegals, b2k, sumdivprod, subsecvmax, dale, bancomat, sume4, alice, porumb1, albine2, culegere, stele1, medalion, cifreco, meteo1, unupatru, xyz, vistiernic, chibrituri, bete1, greieri, interviu, prieten, prize, conturi, numere12, martisoare, piramide, pagini, punctul, tablita, pavare1, ordine, covor1, speciale, echer, numere13
Despre structura alternativa: cuburi3, multimi, ucif, tabel, ocr, numere7, cabina, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, visul, paranteze, copaci1, ogorul, muzeu, timer, triunghi1, piatra, greiere, numerus, ape, ore, pegals, alun, chibrituri, interviu
surse trimise | ajutor