Валера считает, что число красивое, если оно равно 2k или -2k для некоторого целого k (k ≥ 0). Недавно учитель математики попросил Валеру представить число n в виде суммы красивых чисел. Так как Валера очень жадный, он хочет использовать для выполнения этого задания минимально возможное количество красивых чисел.
Помогите Валере, найдите это количество. Другими словами, если мы рассмотрим все разложения числа n на красивые слагаемые, то нужно найти размер разложения, в котором меньше всего слагаемых.
В первой строке задана строка s (1 ≤ |s| ≤ 106), обозначающая двоичное представление числа n без лидирующих нулей (n > 0).
Выведите единственное целое число — минимальное количество красивых чисел, сумма которых равна n.
10
1
111
2
1101101
4
В первом примере n = 2 является красивым числом.
Во втором примере n = 7, и Валера может разложить его в сумму 23 + ( - 20).
В третьем примере n = 109 раскладывается в сумму четырех слагаемых следующим образом: 27 + ( - 24) + ( - 22) + 20.
| Codeforces Round 171 (Div. 2) |
|---|
| Закончено |
