| Fişierul intrare/ieşire: | moneda.in, moneda.out | Sursă | Selectie echipe ACM ICPC, UPB 2009 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.625 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Moneda
Cunoasteti cu totii problema "clasica" a celor N monede (numerotate de la 1 la N), dintre care una este diferita (mai grea sau mai usoara). Pentru a identifica moneda diferita (si a stii daca este mai grea sau mai usoara decat celelalte monezi), aveti la dispozitie o balanta cu 2 talere, cu care puteti efectua cantariri. O cantarire consta in amplasarea a aceluiasi numar de monezi pe fiecare din cele 2 talere (stang si drept). Rezultatul unei cantariri indica daca monezile de pe cele 2 talere au aceeasi greutate, daca cele de pe talerul stang sunt mai grele, sau daca cele de pe talerul drept sunt mai grele. Gigel a efectuat M cantariri in vederea identificarii monezii diferite. Totusi, dupa ce a efectuat cele M cantariri, el nu stie cum sa mai continue, astfel ca va cere ajutorul. Gigel ar vrea sa stie care este numarul minim suplimentar de cantariri ce mai trebuie efectuate in cel mai rau caz pentru a identifica moneda diferita, precum si de a sti daca este mai grea sau mai usoara decat celelalte monezi (cunoscand cantaririle efectuate in prealabil de Gigel, impreuna cu rezultatul acestora).
Date de intrare
Fişierul de intrare moneda.in contine pe prima linie numerele N si T. In continuare, vor fi descrise T teste, fiecare test corespunzand unui caz cu acelasi numar N de monezi. Prima linie ce descrie un test contine numarul M de cantariri efectuate de Gigel. Urmatoarele M linii descriu cantaririle. O linie ce descrie o cantarire are urmatorul format. Primul numar de pe linie este numarul K de monezi ce au fost amplasate pe fiecare din cele 2 talere ale balantei. Urmatoarele K numere de pe linie contin numerele monezilor amplasate pe talerul stang, iar urmatoarele K numere contin numerele monezilor amplasate pe talerul drept. Ultimul numar de pe linie descrie rezultatul cantaririi:
- 0 - daca greutatile monezilor de pe cele 2 talere sunt egale
- -1 - daca monezile de pe talerul stang sunt mai grele
- 1 - daca monezile de pe talerul drept sunt mai grele.
Toate numerele de pe aceeasi linie sunt separate intre ele prin cate un spatiu.
Date de ieşire
În fişierul de ieşire moneda.out veti afisa T linii, cate una pentru fiecare test dat in fisierul de intrare (in ordinea in care sunt date testele). Pe linia corespunzatoare unui test veti afisa un singur numar, reprezentand numarul minim de cantariri suplimentare necesare in cel mai rau caz pentru a identifica moneda diferita (si a sti daca este mai grea sau mai usoara decat celelalte monezi).
Restricţii
- 3 ≤ N ≤ 60
- 1 ≤ T ≤ 10.000
- 0 ≤ M ≤ 10
- 1 ≤ K ≤ N/2
- Se garanteaza ca raspunsurile la cele M intrebari puse de Gigel nu sunt contradictorii.
Exemplu
| moneda.in | moneda.out |
|---|---|
| 8 10 1 1 2 5 0 3 1 2 4 0 2 4 7 5 8 1 1 7 2 1 2 1 7 8 -1 4 7 4 3 6 1 8 2 5 -1 2 2 6 4 2 3 0 1 4 7 0 2 1 7 1 -1 1 7 6 0 0 1 1 6 8 -1 4 1 7 1 0 4 5 1 8 3 4 2 7 6 1 2 4 8 3 1 -1 3 2 3 6 5 1 7 1 4 2 1 3 2 5 1 4 8 7 5 6 4 2 3 1 1 1 8 3 0 4 3 8 1 2 5 4 7 6 -1 3 1 2 7 0 2 8 3 5 4 1 1 6 1 0 | 3 0 1 2 0 3 1 0 0 2 |
| 10 20 1 4 10 5 9 3 6 2 8 7 -1 1 3 3 2 7 9 6 8 0 1 3 3 8 10 6 5 4 0 1 3 5 2 4 9 8 3 1 2 5 2 10 9 7 6 1 3 5 4 8 1 4 9 3 10 2 4 6 5 1 0 2 3 2 6 5 3 1 10 0 5 4 8 3 7 1 2 6 5 10 9 -1 1 4 7 1 4 9 2 3 6 10 1 4 3 6 2 3 1 7 5 0 4 7 2 9 10 5 4 1 8 -1 5 9 4 8 2 1 5 10 7 6 3 1 3 6 4 8 5 9 1 1 3 5 9 2 10 8 3 1 6 7 5 4 1 4 3 5 7 2 9 10 8 6 -1 5 1 4 10 2 9 6 3 7 8 5 1 1 3 9 3 6 5 10 2 -1 2 4 4 10 7 8 6 9 3 5 -1 3 2 7 4 6 3 9 -1 2 3 2 9 7 3 5 10 0 4 6 1 4 7 5 10 3 9 -1 3 3 2 3 6 8 5 10 1 4 1 8 9 4 3 6 10 5 -1 4 3 2 4 6 7 5 1 8 1 0 3 5 8 6 1 5 10 7 9 3 2 4 -1 4 5 9 10 3 1 8 7 6 0 3 8 4 9 5 10 3 0 1 3 5 6 8 10 9 4 -1 2 5 8 2 6 5 1 3 7 4 9 10 1 3 4 9 6 8 1 10 0 3 5 8 9 4 2 1 5 6 7 3 10 -1 3 7 3 8 6 2 4 0 3 10 6 3 7 4 5 0 4 4 10 3 4 8 2 6 9 5 -1 4 2 6 10 1 7 5 4 9 -1 4 2 4 5 8 7 6 3 9 1 5 1 4 2 6 3 8 5 9 7 10 -1 1 5 1 8 10 6 4 5 2 9 3 7 1 | 2 2 2 2 1 2 2 1 2 2 2 1 1 3 0 2 2 1 0 3 |
Explicaţie
Cele 2 exemple de mai sus reprezinta primele 2 teste folosite pentru evaluarea problemei.
