Problem Statement
Given is an undirected tree with N vertices. As usual, vertices are numbered 0 to N-1.
We are going to place some tokens into the vertices of the tree. All tokens are identical. Arbitrarily many tokens can be placed into the same vertex.
Once we are done, our opponent will have the option to move the tokens. In order to make a move, the opponent must always do the following:
- the opponent has to select two tokens that are in the same vertex of the tree,
- they have to remove one of them (as payment for the move)
- then, they may move the other token along an edge of the tree to a different vertex.
The opponent may make as many moves as they like, anywhere where moves can be performed. Each token may be moved arbitrarily many times.
We want to make sure that vertex G remains empty, regardless of what our opponent does. What is the maximum total number of tokens we can place onto the tree? Compute this value and return the remainder it gives modulo 1,000,000,007.
In order to keep the input small, the tree is generated pseudorandomly using the following pseudocode:
state = seed
for i = 1 to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
tmp = (state / 1000) modulo L
p = max(0, i-1-tmp)
add a tree edge that connects vertices i and p
Definition
- Class:
- TreeTokens
- Method:
- placeMax
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int placeMax(int N, int G, int L, int seed)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 100,000, inclusive.
- G will be between 0 and N-1, inclusive.
- L will be between 1 and 10^7, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
5
0
1000000
1234567
Returns: 4
The tree consists of the edges 0-1, 0-2, 0-3, and 0-4. We want to prevent our opponent from getting a token onto vertex 0. The best we can do is to place one token onto each of the other four vertices. This way the opponent cannot make any valid move.
5
4
1
1234567
Returns: 15
The tree consists of the edges 0-1, 1-2, 2-3, and 3-4. We want to prevent our opponent from getting a token onto vertex 4. The best we can do is to take 15 tokens and place all of them onto vertex 0. The opponent will be able to do some moves, but they won't be able to get a token onto vertex 4. Regardless of how we distribute 16 (or more) tokens, the opponent will always have a way to get some token onto vertex 4.
4
0
2
4742
Returns: 4
The intermediate values of the variable "state" are 1599137607, 601115508, 1075423389. (Watch out for integer overflows.) The generated tree edges are 1-0, 2-0, and 3-1.
1
0
7
43634
Returns: 0
2
1
5
23623
Returns: 1
1000
500
1
12523523
Returns: 85724505
100000
0
10000000
2353265
Returns: 102351
100000
0
1
21532
Returns: 303861759
100000
0
2
21532
Returns: 618295921
100000
34643
2
25235
Returns: 923290622
99898
64346
3
326543
Returns: 160899501
99924
23332
7
353353
Returns: 416937444
98698
64654
56
465
Returns: 720939209
98765
12345
432
353
Returns: 933398974
100000
98546
90000
34634634
Returns: 199327
7
5
3
47
Returns: 17
Edges: 0-1, 0-2, 0-3, 3-4, 4-5, 3-6.
99599
2
123
123
Returns: 933233388
9999
8888
5555
7777
Returns: 36860
100000
97872
1298
1219
Returns: 699439932
100000
0
100000
111111
Returns: 183198
100000
0
1000
1234567
Returns: 656070434
100000
12345
34567
45678
Returns: 944968
100000
50
1000
234
Returns: 257858110
100000
0
1232
183428312
Returns: 424422179
300
4
24
35252
Returns: 268838699
100000
0
44
555
Returns: 354875003
10000
65
100
24215
Returns: 344799597
100000
42
1000
0
Returns: 289545720
100000
38482
999997
241243
Returns: 107427
100000
1
1637232
12345
Returns: 105076
10
0
7
1
Returns: 15
100000
10
1000
1231234
Returns: 385149173