Fişierul intrare/ieşire:ciocolata.in, ciocolata.outSursăONI 2014, Baraj
AutorAdrian PanaeteAdăugată depas.andreiPopovici Andrei-Sorin pas.andrei
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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:

  1. Dacă batonul are două tablete, îl rupe în două tablete pe care le mănâncă.
  2. 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ă.
  3. 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.inciocolata.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?