Codeforces Beta Round 75 (Div. 2 Only) |
---|
Закончено |
Маленький морж Клычок очень любит математику. Поэтому, когда ему скучно, он играет с числом, выполняя некоторые операции.
Клычок берет некоторое положительное целое число x, и хочет получить из него единицу. Пока x не равно 1, Клычок повторяет следующее действие: если x нечетное, то он прибавляет к нему 1, иначе он делит x на 2. Клычок знает, что для любого целого положительного числа этот процесс завершается за конечное время.
Сколько действий нужно Клычку, чтобы получить из числа x единицу?
В первой строке записано целое положительное число x в двоичной системе счисления. Гарантируется, что первая цифра x отлична от нуля и количество разрядов в нем не превышает 106.
Выведите необходимое количество действий.
1
0
1001001
12
101110
8
Рассмотрим третий пример. Число 101110 четно, значит разделим его на 2. После деления Клычок получает нечетное число 10111 и прибавляет к нему единицу. Число 11000 можно поделить на 2 три раза подряд, и получить число 11. Осталось увеличить число на единицу (получим 100), и затем два раза поделить его на 2. В итоге получается 1.
Название |
---|