Problem E
Exact Change
While in Binaria, you find a store where you want to buy
some presents for your friends. In Binaria, the currency is
bits, and the coin denominations are the set of all integer
powers of
When you make a purchase, you must pay with exact change. You have an unlimited number of bits that you can access from your bank account, but you can choose to withdraw them in whatever denominations you find most convenient. Carrying many coins is inconvenient though, so you wish to minimize the number of coins you carry with you.
Compute the minimum number of coins you need to bring with
you such that you can pay any integer amount of bits between
Input
The first line of input contains a single integer
The second line of input contains a single integer
Output
Output a single integer
Sample Input 1 | Sample Output 1 |
---|---|
10101 101010 |
6 |
Sample Input 2 | Sample Output 2 |
---|---|
100 101 |
2 |