| Fişierul intrare/ieşire: | joc8.in, joc8.out | Sursă | Grigore Moisil 2008, clasele 5-6 |
| Autor | Clara Ionescu | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 4736 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc8
Gigel si Alina se joaca de-a ghicitoarea. Gigel se gandeste la un numar natural mai mare sau egal decat un anumit numar x si mai mic sau egal decat un alt numar y. Alina ii promite lui Gigel ca va ghici la ce numar s-a gandit Gigel punandu-i un numar surprinzator de mic de intrebari de urmatoarele forme:
- Te-ai gandit la numarul z?
- Numarul tau este mai mic decat z?
Urmeaza ca Gigel sa-i raspunda numai cu Da sau Nu dupa caz. Gigel este neincrezator deoarece nu stie cum va proceda Alina. Noi in schimb va spunem secretul Alinei. Ea va calcula numarul natural z aflat la mijlocul intervalului [x, y] si va intreba: "Te-ai gandit la z?". Daca raspunsul lui Gigel este Da, jocul s-a terminat, deoarece Alina a ghicit numarul la care s-a gandit Gigel. Daca raspunsul este Nu, Alina va intreba "Numarul tau este mai mic decat z?".
- Daca acum raspunsul este Da, Alina va calcula numarul natural aflat la mijlocul intervalului [x, z-1] si va pune din nou intrebarea 1.
- Daca raspunsul este Nu, Alina va calcula numarul natural aflat la mijlocul intervalului [z + 1, y] si va pune din nou intrebarea 1.
Intrebarile Alinei vor continua in mod similar, pana cand ghiceste numarul la care s-a gandit Gigel. Numai ca Gigel este smecher si este posibil ca el sa incerce s-o pacaleasca pe Alina si sa dea cel putin un raspuns gresit. In cazul acesta Alina isi va da seama ca a fost pacalita in momentul in care marginea din stanga a intervalului curent devine mai mare decat marginea din dreapta.
Cerinta
Scrieti un program care simuleaza jocul descris.
Date de intrare
Pe prima linie a fisierului de intrare joc8.in se afla doua numere naturale x si y reprezentand limitele intre care a ales Gigel un numar. Pe urmatoarele linii sunt scrise raspunsurile lui Gigel. Daca raspunsul este Da, in fisier este scrisa cifra 1. Daca raspunsul este Nu, in fisier este scrisa cifra 0. Intotdeauna sunt atatea raspunsuri cate intrebari a pus Alina.
Date de iesire
Pe prima linie a fisierului de iesire joc8.out se va scrie numarul natural la care s-a gandit Gigel. In cazul in care Gigel triseaza, pe prima linie se va scrie numarul 0.
Restrictii
- 1 ≤ x, y ≤ 10 000
Exemple
| joc8.in | joc8.out |
|---|---|
| 100 300 0 0 0 1 0 0 1 | 237 |
| 25 30 0 0 0 0 0 0 | 0 |
Explicatie
Pentru primul exemplu, Alina face urmatoarele presupuneri (mai jos prin [expresie] am notat partea intreaga a expresiei):
- [(100 + 300)/2] = 200 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Nu)
- [(201 + 300)/2] = 250 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Da)
- [(201 + 249)/2] = 225 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2 si raspuns Nu)
- [(226 + 249)/2] = 237 (intrebare de tip 1, raspuns Da)
Pentru al doilea exemplu, Alina face presupunerile:
- [(25 + 30)/2] = 27 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
- [(28 + 30)/2] = 29 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
- [(30 + 30)/2] = 30 (intrebare de tip 1, raspuns Nu, apoi intrebare de tip 2, si raspuns Nu)
- [(31 + 30)/2] = nu se mai calculeaza, deoarece x a devenit mai mic decat y. Rezulta ca Gigel a trisat.
