NoDistanceD
SRM 850 · 2023-10-25 · by misof
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.
Constraints
- N will be between 1 and 10^12, inclusive.
- D will be between 1 and 10^12, inclusive.
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.
123456789012 123456789012 Returns: 123456789012
123456789012 123456789011 Returns: 123456789012
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NoDistanceD with a public method long long count(long long N, long long D) · 100 test cases · 2 s / 256 MB per case