Задача №1819. Иван-царевич и змеёныши
Прошёл Иван-царевич сквозь заколдованный дремучий лес невредимым и вышел в поле. А на опушке засада устроена: Змей Горыныч послал своих змеёнышей, чтобы царевича погубить. Достал тут Иван-царевич свой верный меч и стал рубиться со змеёнышами — не на жизнь, а на смерть!
Только вот беда: вначале у каждого змеёныша одна голова, но от ранений количество голов увеличивается. Только если снести змеёнышу одним махом все головы, они разом падают наземь, и змеёныш погибает, а змеиное тулово рассыпается в прах. Но если ранит Иван-царевич змеёныша, и не все головы сносит одним ударом — тотчас раны заживают, головы прирастают обратно, да вдобавок на месте каждой головы вырастает по две. Ранил Иван-царевич одного змеёныша — стало у него две головы, ранил его ещё раз — стало четыре. Теперь, если не удастся одним махом все четыре головы снести — восемь станет!
Долго ли бились, коротко ли — поняли оставшиеся в живых змеёныши, что не одолеть им Ивана-царевича, расправили крылья да и улетели восвояси.
Тут, откуда ни возьмись, из кустов вылез старичок-сказитель и молвил:
— Спасибо тебе, Иван-царевич, ты меня от верной смерти спас! За это я буду век по городам и сёлам ходить и о тебе сказ сказывать. Скажи, сколько змеёнышей ты положил?
— Не моё это богатырское дело, счётом заниматься! — отвечал Иван-царевич. — Вон, возьми сам головы да посчитай.
— Голов, вижу, много, да только одна голова — это ещё не один змеёныш. Если я буду по головам считать, никто мне, старому, не поверит, и над тобой народ только смеяться будет. Раз такое дело, буду рассказывать, что змеёнышей было минимальное число такое, чтобы от них могло столько голов остаться.
Так молвил, да и растворился в воздухе. А Иван-царевич призадумался: а что же о нём будет рассказывать сказитель?
Зная, сколько змеиных голов осталось на поле после битвы со змеёнышами, выясните, какое минимальное количество змеёнышей мог убить Иван-царевич. Помните, что каждому змеёнышу можно отсечь только сразу все головы, которые у него есть — иначе ни одна голова не падает, а вместо этого их количество удваивается.
В первой строке входного файла задано целое число \(n\) — количество змеиных голов на поле битвы (0 \(\le\) \(n\) \(\le\) \(10^9\)).
В первой строке выходного файла выведите одно число — минимальное количество змеёнышей, убитых Иваном-царевичем.
В первом примере две головы могло получиться, если Иван-царевич убил двух змеёнышей с первого удара, или же если он ранил, а затем убил всего одного змеёныша. Значит, минимальное количество змеёнышей равно единице.
Во втором примере три головы могло получиться в следующих случаях:
Иван-царевич убил трёх змеёнышей с первого удара;
Иван-царевич убил одного змеёныша с первого удара, а другого — со второго удара.
2
1
3
2