| Fişierul intrare/ieşire: | ciocolata.in, ciocolata.out | Sursă | ONI 2014, Baraj |
| Autor | Adrian Panaete | Adăugată de |  Popovici Andrei-Sorin •pas.andrei |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ciocolata
Pe o masă se găsesc batoane de ciocolată. Fiecare baton de ciocolată este format din cel puţin 2 şi cel mult 16 tablete.
Două fete – A şi B, joacă un joc în care fiecare mută alternativ, A efectuând prima mutare. Fata aflată la mutare trebuie să aleagă unul dintre batoanele rămase pe masă şi să folosească una dintre următoarele variante:
- Dacă batonul are două tablete, îl rupe în două tablete pe care le mănâncă.
- Dacă batonul are cel puţin trei tablete rupe o tabletă dintr-un capăt, o mănâncă şi lasă batonul rămas pe masă.
- Dacă batonul are cel puţin patru tablete, îl rupe în două batoane de cel puţin două tablete şi lasă cele două batoane pe masă fără să mănânce nimic.
În tabelul de mai jos sunt explicate mutările care pot fi aplicate pentru batoane de 2, 3, 4 şi 5 tablete, în coloana din dreapta fiind înnegrite tabletele care trebuie mâncate la mutarea corespunzătoare.
Jocul se termină când se nu mai este ciocolată pe masă. Scopul jocului este pentru fiecare fată să mănânce cât mai puţină ciocolată (fetele nu vor să se îngraşe). Se ştie că cele două concurente sunt extrem de inteligente deci fiecare joacă optim.
Cerinţa
Pentru t configuraţii ale jocului în care se cunosc numerele de batoane de fiecare tip să se stabilească numărul de tablete mâncate de fiecare fată la finalul jocului.
Date de intrare
Fişierului de intrare ciocolata.in conţine pe prima linie un număr natural t – reprezentând numărul de configuraţii ale jocului la care trebuie să se găsească raspunsul. Următoarele t linii descriu câte o configuraţie a unui joc. Fiecare dintre aceste linii conţin câte 15 numere naturale - separate prin câte un spaţiu - c2, c3, c4, ..., c16 reprezentând numărul de batoane de 2, 3, 4, ...,16 tablete aflate pe masă la începutul jocului.
Date de ieşire
Fişierului de ieşire ciocolata.out se va conţine t linii descriind rezultatul celor t configuraţii din fişierul de intrare. Pe fiecare dintre aceste linii se vor scrie câte două numere naturale x şi y – separate prin spaţiu, x- reprezentând numarul de tablete mâncate de A iar y- numărul de tablete mâncate de B la jocului corespunzător din fişierul de intrare.
Restricţii
- 1 ≤ t ≤ 30 002
- Pentru 30% din teste, pentru fiecare din cele t configuratii vor fi doar batoane de dimensiune 2, 3, 4, sau 5.
- Pentru fiecare dintre cele t configuraţii numărul de batoane de fiecare tip este număr natural şi nu depaşeşte 30 002.
Exemplu
| ciocolata.in | ciocolata.out |
|---|---|
| 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 3 2 |
Explicaţie
Pe masă avem un baton de 2 şi unul de 3
A rupe batonul de 3 şi mănâncă 1.
B rupe unul dintre batoanele de 2 rămase şi mănâncă 2.
A rupe batonul de 2 rămas, mănâncă 2 şi jocul se termină.
O altă variantă ar fi fost:
A rupe batonul de 2 şi mănâncă 2.
B rupe batonul de 3 ramas şi mănâncă 1 A rupe batonul de 2 rămas, mănâncă 2 şi jocul se termină.
Această variantă este incorectă pentru că A nu a jucat optim.
