Fişierul intrare/ieşire:balanta.in, balanta.outSursăpreONI 2007, runda 3
AutorAdrian VladuAdăugată deazotlichidAdrian Vladu azotlichid
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Balanta

Chernel Camatarul are probleme. A primit de la un client N monede identice presupuse a fi din aur, dar el banuieste ca exact una dintre acestea este falsa. Chernel stie ca moneda falsa este ori mai grea, ori mai usoara decat cele din aur, toate celelalte avand mase egale. Pentru a verifica, el foloseste o balanta cu ajutorul careia executa M cantariri. La fiecare cantarire pune un numar egal de monede pe cele doua talere si isi noteaza rezultatul. Din pacate, Chernel actioneaza destul de haotic, iar la final nu stie daca in urma cantaririlor poate determina cu precizie moneda falsa.

Ajutati-l sa afle raspunsul!

Date de intrare

De pe prima linie a fisierului de intrare se citesc doua numere intregi N si M. Urmeaza M linii, fiecare fiind descrisa in felul urmator: un numar k, reprezentand numarul de monede asezat pe fiecare din cele doua talere ale balantei, k numere intregi intre 1 si N reprezentand monedele asezate pe talerul stang, alte k numere intregi intre 1 si N reprezentand monedele asezate pe talerul drept, alaturi de un numar r din multimea {0, 1, 2}. r indica rezultatul cantaririi, acesta fiind 0 daca balanta ramane in echilibru, 1 daca talerul stang este mai greu decat cel drept, respectiv 2 daca talerul drept este mai greu decat cel stang.

Date de iesire

Prima linie a fisierului de iesire contine un numar intreg intre 1 si N, reprezentand moneda falsa in cazul in care aceasta se poate determina cu precizie, respectiv 0 in cazul in care cantaririle lui Chernel nu au fost suficiente pentru a gasi moneda respectiva.

Restrictii

  • 1 ≤ N, M ≤ 1024

Exemplu

balanta.inbalanta.out
8 3
4 1 2 3 4 5 6 7 8 1
1 1 2 0
1 3 4 2
4
4 2
2 1 2 3 4 2
1 2 3 2
0

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content