ZEROCNT - Zero Count
Write down N integers 1, 2 ... N in binary system on a paper, one per line, ignore all leading 0s:
1
10
11
100
101
110
111
...
Now on each line, consider all groups of consecutive 0s, index these group from 1. We will color all zeros in the 1st, (K+1)th, (2K+1)th, ... group, for K is a given integer.
For example: if a number in binary is: 10100011100110000, and K = 2. We have 4 groups of consecutive 0s, and we will color all zeros in the 1st and the 3rd group. So we will color 1 + 2 = 3 zeros in this line.
Given N and K. Compute total number of 0s we will color in the paper. (The paper is big enough to contain all numbers :D)
Input
Several lines, each line contains 2 integers: N and K separated by a single space. (1 < N < 231, K > 0)
Output
For each line in the input, print exactly 1 number on a single line which is the result of the corresponding test case.
Example
Input:
4 1
56 2
Output:
3
92
hide comments
The Vagabond:
2012-07-23 23:54:45
Input: Several lines??? aWWWWWWWWWWWW.
|
|
cracks:
2011-05-26 10:00:31
why i am getting time limited exceeded,is there any other algorithm to get binary values of a number in min time,except divisin method,i cant get what part of my solution is taking such a time
|
|
The Bumblebee:
2011-02-12 18:27:30
What's the criteria for end of input? |
|
numerix:
2011-02-10 05:35:36
Is there any good reason for this really strange language restriction? If not, please open it for more/all languages.
|
Added by: | Race with time |
Date: | 2011-02-05 |
Time limit: | 0.106s |
Source limit: | 700B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | VOJ |