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 de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile 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.