MaximizeValue
SRM 840 · 2022-10-24 · by misof
Problem Statement
A castle has N > 1 rooms, numbered 0 to N-1.
A knight can attempt to collect gold from the castle. At the beginning of the attempt, exactly x gold coins are placed into room x, for all x. To start the attempt, the knight must choose a single non-negative integer S smaller than N. This number S will remain constant during the entire attempt.
The only door to the castle leads to room 1. The knight can use this door to enter the castle and start the attempt. At any point when in room 1, the knight can also use the door to end the attempt and leave the castle.
Whenever in a room number x, the knight has two options:
- Collect all gold coins from this room.
- Move to the room number (x*S) modulo N.
Given is a prime number P > 2 and a positive integer K. The number N of rooms in the castle is 2*(PK). In words: N is twice the value of P to the power of K.
Help the knight: for the given N find and return any choice of S that can be used to maximize the amount of coins with which the knight can leave the castle.
Notes
- During an attempt the coins in each room can only be collected once. Once the knight collects them, the room is now empty for the rest of the attempt.
Constraints
- P will be at least 3.
- P will be a prime number.
- K will be at least 1.
- N = 2*P^K will not exceed 10^14.
3 1 Returns: 5
We have N = 2*(3^1) = 2*3 = 6. For S = 5 the knight can enter the castle, start the attempt in room 1, go to room 5, collect the 5 coins there, go to room (5*5) mod 6 = 1, collect the 1 coin there, and leave the castle with 5+1 = 6 coins. For S = 1 the knight has the option to go from room 1 to room 1, but that clearly does not help. The knight can only collect the 1 gold coin in room 1. For any other S the knight can only enter the castle, pick up the one coin from room 1 and leave immediately. Any attempt to move to a different room leads to a situation in which the knight remains stuck in the castle forever. The knight may collect more coins (for S = 2 the knight can collect 1+2+4 = 7 coins), but that does not count as the knight is unable to bring those 7 coins out of the castle. Hence, the correct return value is 5.
7 2 Returns: 47
Here N = 2 * 7^2 = 98. The choice S = 47 allows the knight to leave the castle with 2058 gold coins. No other choice of S is better. Several other choices of S lead to the same outcome as S = 47. These would also be accepted as correct answers.
999999937 1 Returns: 392783989
7071061 2 Returns: 6352677
3 28 Returns: 22876792454963
Submissions are judged against all 141 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaximizeValue with a public method long long solve(long long P, int K) · 141 test cases · 2 s / 256 MB per case