Fişierul intrare/ieşire:	joc4.in, joc4.out	Sursă	Teza Vianu 2014 clasa a 10-a
Autor	Victor Manz	Adăugată de	Victor Manz •vmanz
Timp execuţie pe test	0.1 sec	Limită de memorie	2048 kbytes
Scorul tău	N/A	Dificultate	3/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Joc4 (clasa a 10-a)

Bălănel a primit de curând un joc nou. Acesta conţine N monede şi o balanţă cu două talere. Una dintre monede este falsă, fiind mai uşoară decât celelalte N–1. Jocul constă în găsirea monedei false după cât mai puţine cântăriri. Fiind un bun informatician, Bălănel şi-a dat seama că, jucând optim, nu are nevoie de mai mult de Q cântăriri pentru a găsi moneda falsă, indiferent de poziţia iniţială a acesteia.
Miaunel, prietenul pus pe şotii al lui Bălănel, îşi doreşte să ia cât mai multe dintre monede fără ca amicul său să îşi dea seama. Strategia lui Miaunel se bazează pe faptul că Bălănel nu numără niciodată câte monede sunt la început, ci doar după câte cântăriri o găseşte pe cea falsă. Prin urmare Miaunel va lua numărul maxim de monede K, astfel încât, oricât de bine ar juca Bălănel, să existe situaţii în care acesta să nu poată să gasească moneda falsă după mai puţin de Q cântăriri în jocul rămas cu N–K monede.
De exemplu, dacă valoarea iniţială a lui N este 5, atunci Q este 2. Bălănel pune mai întâi câte două monede pe fiecare taler. Dacă balanţa este în echilibru, atunci moneda care nu a fost cântărită este cea falsă şi nu mai e nevoie de alte operaţii. Dacă însă unul dintre talere atârnă mai puţin, atunci moneda falsă se află printre cele două de pe acest taler şi pentru găsirea ei mai e nevoie de o cântărire. Prin urmare Q este 2 (în cazul cel mai rău, Bălănel descoperă moneda falsă după 2 cântăriri).
Miaunel poate lua în acest caz cel mult o monedă pentru că dacă ar lua două (rămânând astfel 3), atunci lui Bălănel i-ar fi suficientă o cântărire pentru a o găsi pe cea falsă. (Pune câte o monedă pe fiecare taler şi dacă balanţa e în echilibru, atunci cea de-a treia e mai uşoară. Dacă un taler atârnă mai puţin, atunci moneda aflată pe acesta e cea falsă. Deci indiferent de rezultatul cântăririi Bălănel a aflat care e moneda pe care o căuta după o cântărire.)

Cerinţă

Nefiind foarte bun la calcule, Miaunel vă roagă să-l ajutaţi să rezolve această problemă, scriind un program care să determine cel mai mare K cu proprietatea de mai sus pentru un N oarecare dat.

Date de intrare

În fişierul de intrare joc4.in se află pe prima linie un număr natural nenul N, reprezentând numărul total de monede ale jocului.

Date de ieşire

În fişierul de ieşire joc4.out se va scrie pe prima linie numărul maxim de monede K, pe care le poate lua Miaunel astfel încât Bălănel să găsească moneda falsă după la fel de multe cântăriri în cazul cel mai puţin favorabil, oricât de bine ar juca.

Restricţii

• 1 ≤ N ≤ 1 000 000 000

Exemplu

Explicaţie

Ca să găsească moneda falsă, Bălănel poate proceda în felul următor: pune câte 3 monede pe fiecare taler. Cazul cel mai puţin favorabil e cel în care balanţa nu e în echilibru. Atunci moneda falsă e printre cele trei de pe talerul care atârnă mai puţin şi pentru determinarea ei mai e nevoie de o cântărire, deci în total au fost necesare Q=2 cântăriri.
O altă strategie ar fi ca iniţial să pună câte 2 monede pe fiecare taler. Atunci, în caz de echilibru, moneda falsă e printre cele care nu au fost cântărite, iar dacă un taler atârnă mai puţin, e printre cele de pe acesta. În ambele situaţii mai e nevoie de o cântărire, deci se ajunge tot la Q=2.
Pentru N=6, N=5 şi N=4, moneda nu poate fi găsită în cazul cel mai rău după mai puţin de 2 cântăriri, în schimb pentru N≤3 Bălănel poate găsi moneda căutată cu mai puţin de 2 cântăriri. Prin urmare Miaunel poate lua cel mult 3 monede, astfel încât Bălănel să nu îşi dea seama.