Connection Status:
Competition Arena > TheDivisionGame

TheDivisionGame

SRM 565 · 2012-06-05 · by gojira_tc

SRM 565 · 2012-06-05 · by gojira_tc · Dynamic Programming, Math
Class Name: TheDivisionGame
Return Type: long
Method Name: countWinningIntervals
Arg Types: (int, int)
Problem Statement

Problem Statement

Manao likes to play the Division Game with his friends. This two-player game is played with some collection of natural numbers S. Manao plays first and the players alternate in making a move. A move is choosing some number X from S and a natural number Y &gt 1 such that Y divides X. Then, X is replaced by X / Y in the collection. Note that at any moment the collection may contain multiple copies of the same number. The game proceeds until no more moves can be made. The player who managed to make the last move is declared the winner.

Since hot debates arise on what numbers should be in S, the friends decided to regularize their choice. They always choose a contiguous interval of numbers [A, B] to be the initial collection S. That is, at the beginning of the game, the collection S contains each of the integers A through B, inclusive, exactly once. Manao knows that A and B will satisfy the condition L &le A &le B &le R. You are given the ints L and R. Count the number of such intervals for which Manao will win the Division Game given that both players play optimally.

Notes

  • Only one number from the collection changes in each move. For example, if the collection contains three copies of the number 8, and the player chooses X=8 and Y=4, only one of the 8s in the collection will change to a 2.

Constraints

  • L will be between 2 and 1,000,000,000, inclusive.
  • R will be between L and L + 1,000,000, inclusive.
Examples
0)
9
10
Returns: 2

If the chosen interval is [9,9] or [10,10], the collection S contains only one number. In these two situations Manao can win the game in a single move. On the other hand, if the chosen interval is [9,10], Manao will lose to an optimally playing opponent.

1)
2
5
Returns: 9

The only case where Manao loses is if the game starts with the interval [2,3]. Note that if the starting interval is [2,5], Manao can choose X=4 and Y=2 in his first move. After that move, the collection will contain the values 2, 2, 3, and 5.

2)
2
6
Returns: 13

Manao will also lose the game if the starting interval is [3,6].

3)
2
100
Returns: 4345
4)
2
1000000
Returns: 484332732439

Submissions are judged against all 67 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheDivisionGame with a public method long long countWinningIntervals(int L, int R) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous