В городе Санкт-Петербург день длится $$$2^{100}$$$ минут. С главной станции города Санкт-Петербург поезда отъезжают в моменты времени $$$1$$$ минута, $$$4$$$ минуты, $$$16$$$ минут и т. д., то есть в моменты времени $$$4^k$$$ для целых $$$k \geq 0$$$. Team BowWow прибыли на станцию в момент времени $$$s$$$ и хотят понять, сколько поездов они уже пропустили, то есть сколько поездов отъехало со станции строго раньше, чем в момент времени $$$s$$$. Например, если $$$s = 20$$$, то они пропустили поезда, отъехавшие в моменты времени $$$1$$$, $$$4$$$ и $$$16$$$. Так как время знаете только вы, подскажите им!
Обратите внимание, что число $$$s$$$ будет дано вам в двоичной системе счисления без ведущих нулей.
Первая строка содержит единственное число $$$s$$$ ($$$0 \leq s < 2^{100}$$$), представленное в двоичной системе счисления без ведущих нулей.
Выведите одно число — количество поездов, отправившихся со станции строго раньше, чем в момент времени $$$s$$$.
100000000
4
101
2
10100
3
В первом примере $$$100000000_2 = 256_{10}$$$, пропущенные поезда отъехали в моменты времени $$$1$$$, $$$4$$$, $$$16$$$, $$$64$$$.
Во втором примере $$$101_2 = 5_{10}$$$, поезда отъезжали в моменты времени $$$1$$$ и $$$4$$$.
Третий пример был разобран в условии.
| Codeforces Round 581 (Div. 2) |
|---|
| Закончено |
