Problem Statement
Little Maurice has a bag with N balls, numbered from 1 to N.
He draws the balls from the bag, one at a time.
He stops immediately after he removes a ball that differs from any of the previously removed balls by exactly D. If that never happens, he also stops after drawing the last ball from the bag.
Calculate and return the largest possible number of balls Maurice might remove from the bag during the activity described above.
Definition
- Class:
- NoDistanceD
- Method:
- count
- Parameters:
- long, long
- Returns:
- long
- Method signature:
- long count(long N, long D)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^12, inclusive.
- D will be between 1 and 10^12, inclusive.
Examples
5
1
Returns: 4
As D=1, Maurice stops as soon as he sees two balls with consecutive numbers. Sometimes the process will end right after the second ball is drawn, e.g., if he draws 3 followed by 4, or if he draws 3 followed by 2. Sometimes the process ends after the third ball, e.g., if he draws the balls in order 1, 4, 3. The longest the process can take is four balls. For example, Maurice could draw the balls in the order 1, 5, 3, 4.5
2
Returns: 4
Again, the maximum number of balls Maurice can draw is four. This time some valid orders in which he can draw four balls include 1, 5, 4, 3 and 2, 1, 5, 4.123456789012
234567890123
Returns: 123456789012
As no two balls in Maurice's bag differ by 234567890123, he will keep on drawing until he empties the whole bag.12
3
Returns: 7