Codeforces 92B - Binary Number
Little walrus Fangy loves math very much. That’s why when he is bored he plays with a number performing some operations.
Fangy takes some positive integer x and wants to get a number one from it. While x is not equal to 1, Fangy repeats the following action: if x is odd, then he adds 1 to it, otherwise he divides x by 2. Fangy knows that for any positive integer number the process ends in finite time.
How many actions should Fangy perform to get a number one from number x?
Input:
The first line contains a positive integer x in a binary system. It is guaranteed that the first digit of x is different from a zero and the number of its digits does not exceed 106.
Output:
Print the required number of actions.
範例:
input:
1 | 1 |
output:
1 | 0 |
input:
1 | 1001001 |
output:
1 | 12 |
input:
1 | 101110 |
output:
1 | 8 |
Note:
Let’s consider the third sample. Number 101110 is even, which means that we should divide it by 2. After the dividing Fangy gets an odd number 10111 and adds one to it. Number 11000 can be divided by 2 three times in a row and get number 11. All that’s left is to increase the number by one (we get 100), and then divide it by 2 two times in a row. As a result, we get 1.
題意:
他給你一個二進制碼，而當他為偶數時除以2，反之加1，直到數字為1為止，計算他總共做了幾次更動。
思路:
用字串儲存數字，判斷最後的位數如果是1，進位往前直到0，經過的位數做更改，如果進位超出範圍在前面加上1，如果是0消除它，以上做一次判斷計數加1。直到整個字串為1
進階:
一樣用字串儲存做一次迴圈確認為1的字元大於等於2個，成立在右到左第1個1字元之後的0，確認有幾個加上1再加上整個字串的長度就是答案了。
不成立則是屬出0的個數就是答案了。