Šeštadieninė informatikos olimpiadininkų mokykla

Vakar buvo Pauliaus gimtadienis ir jis su Andriumi žaidė spėjimo žaidimą: Andrius bandė atspėti Pauliaus amžių. Andrius žinojo, kad Pauliaus amžius yra sveikas skaičius tarp 1 ir n, imtinai. Andrius gali spėti bet kokį skaičių nuo 1 iki n ir Paulius pasakys šio skaičiaus ir jo amžiaus didžiausią bendrąjį daliklį.

Štai kaip galėjo vykti žaidimas su . Andrius pradeda spėdamas 3, Paulius atsako, kad jo amžiaus ir 3 didžiausias bendrasis daliklis yra 1. Tai reiškia, kad Pauliaus amžius nėra 3 ar 6, tačiau vis dar gali būti 1, 2, 4 arba 5. Andrius spėja 2, Paulius atsako 2. Pauliaus amžius negali būti 1 ar 5, likę variantai yra 2 arba 4 metai. Galiausiai Andrius spėja 4 ir Paulius atsako 2. Taigi, Pauliaus amžius yra 2 ir žaidimas baigtas.

Andriui prireikė trijų spėjimų, tačiau įmanoma nustatyti Pauliaus amžių daugiausia dviem spėjimais, kai . Optimali Andriaus strategija yra: pirmas spėjimas turi būti 6. Jei Paulius atsako 1, tai jo amžius gali būti 1 arba 5; tą galima patikrinti spėjant 5. Jei Paulius atsako 2, tai gali būti 2 arba 4; patikrina spėdamas 4. Jei Paulius atsako 3, tai iškart žinome, kad atsakymas 3. Jei atsako 6, tai atsakymas 6.

Kiek spėjimų blogiausiu atveju reikia duotam n, jei Andrius spėlioja optimaliai?

Pradiniai duomenys

Vienintelėje eilutėje yra vienas sveikasis skaičius n ().

Rezultatai

Vienintelėje eilutėje turi būti vienas sveikasis skaičius - kiek spėjimų Andriui reikės blogiausiu atveju.

Pavyzdys

6

2