Problem Statement
P players are going to attempt crossing a bridge, one player at a time. The players are numbered from 0 to P-1 in the order in which they will do so.
The bridge consists of S sections. The sections are numbered from 0 to S-1 along the bridge. When crossing the bridge, each player must step on each section of the bridge in that order.
Initially, each section consists of two glass panels: a left one and a right one. In each section exactly one of the panels is safe, while the other will break under the weight of a contestant. Whenever that happens, the contestant falls from the bridge, and by that their attempt to cross the bridge terminates.
The players all know this information but they don't know which panel in which section is the safe one.
Of course, the players gather and remember new information during the process. Once a player safely stands on a panel, the following players will already know that the panel is safe. And once a panel breaks, the remaining players can deduce that the other panel in that section must be the safe one.
Players with even numbers (0, 2, 4, ...) all follow the same strategy: if you know which panel is safe in the next section, step on that one, otherwise step on the left panel.
Players with odd numbers (1, 3, 5, ...) also all follow the same strategy: if you know which panel is safe in the next section, step on that one, otherwise step on the right panel.
The people who were setting up the game used a non-random pattern for the safe panels: prime numbers. If the number of the section is prime (2, 3, 5, 7, 11, ...), the left panel is the safe one. For all other sections (0, 1, 4, 6, 8, 9, 10, ...) the right panel is the safe one.
The players never realize this, they follow the strategies described above until the end of the game.
Return the number of players who will successfully cross the bridge.
Definition
- Class:
- SquidGamesBridge
- Method:
- cross
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int cross(int P, int S)
- (be sure your method is public)
Notes
- A positive integer is prime if it has exactly two positive integer divisors. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19. (Notably, the numbers 0 and 1 are not prime.)
Constraints
- P will be between 1 and 10^9, inclusive.
- S will be between 1 and 200,000, inclusive.
Examples
3
2
Returns: 2
Three players and a bridge with two sections. In both sections the right panel is safe. The players cross as follows: Player 0 knows nothing about section 0, so they step on the left panel. It breaks and player 0 is out. Player 1 can deduce that the right panel in section 0 must be safe, so they step on it. Player 1 knows nothing about section 1, so they step on the right panel. It is safe. Player 1 steps off the bridge, crossing it successfully. Player 2 knows that the right panel in section 0 is safe, so they step on it. Player 2 knows that the right panel in section 1 is safe, so they step on it. Player 2 steps off the bridge, crossing it successfully. Two of the three players were successful.
3
4
Returns: 1
Now we extended the bridge to four sections. In this example player 1 will break the right panel in section 2, and then player 2 will safely cross section 2 and follow that by choosing the left panel in section 3. That turns out to be the correct choice, so player 2 successfully crosses the bridge.
3
5
Returns: 0
Here, player 2 will make the incorrect choice in section 4. Nobody crosses the whole bridge.
1234567
1
Returns: 1234566
Everybody other than player 0 will be successful here.
1234
567
Returns: 1029
987654123
199989
Returns: 987618158
4364363
178967
Returns: 4331872
76543
87654
Returns: 59520
9876
87654
Returns: 0
1
1
Returns: 0
2
1
Returns: 1
1
2
Returns: 0
1
100000
Returns: 0
1000000000
1
Returns: 999999999
532653263
3434
Returns: 532652303
75575855
46778
Returns: 75566188
200000
200000
Returns: 164034
3265236
187623
Returns: 3231295
14
1566
Returns: 0
999999999
198765
Returns: 999964232