PrettyLiar
TCO19 SRM 758 · 2019-05-09 · by IH19980412
Problem Statement
This problem has a non-standard time limit: 4 seconds.
Kaede and Kanade are good friends. Today they are going to play a game!
At the beginning of the game, each of them has a sequence of N positive integers. You are given these sequences in the
There is also a single pile of stones. At the beginning of the game the pile consists of S stones. It is guaranteed that S <= sum(kaede) + sum(kanade).
During the game, the players take alternating turns removing some stones from the pile. Kaede takes the first turn. The game is completely deterministic. Each turn looks as follows:
- The player notes the value X of the first element of her sequence.
- The player erases the first element of her sequence.
- The player takes X stones from the pile (or all stones if there are fewer than X stones left).
- If the pile just became empty, the player loses the game.
Both girls call themselves "pretty liars", so you should not be surprised that they are going to cheat: before the game, each girl will choose one of the N! possible permutations and use it to permute her sequence in secret.
You, watching the whole process, come up a question: How many of all (N!)^2 possible scenarios will end with Kaede winning the game?
Please compute and return the answer modulo 1,000,000,007.
Notes
- The constraint on S ensures that one of the girls has to lose the game.
Constraints
- N will be between 1 and 100, inclusive.
- kaede will contain exactly N elements.
- kanade will contain exactly N elements.
- Each element in kaede will be between 1 and 100, inclusive.
- Each element in kanade will be between 1 and 100, inclusive.
- S will be between 1 and 20,000, inclusive.
- S will be less than or equal to the sum of elements in kaede and kanade.
60
{10,40}
{20,30}
Returns: 2
There are four possibilities: kaede:{10,40} kanade:{20,30} kaede:{10,40} kanade:{30,20} kaede:{40,10} kanade:{20,30} kaede:{40,10} kanade:{30,20} In the first case the game will play out as follows: Kaede removes 10 stones from the pile. After the turn, Kaede's sequence is {40} and there are 50 stones left in the pile. Kanade removes 20 stones from the pile. After the turn, Kanade's sequence is {30} and there are 30 stones left in the pile. Kaede is supposed to take 40 stones. As there are only 30 stones left, she takes those 30 stones and loses the game. Hence, Kanade wins. Kaede wins in two out of the four possibilities listed above: the third and the fourth one. Thus, the correct return value is 2.
100
{10,40}
{20,30}
Returns: 4
Regardless of how the girls permute their sequences, Kanade will always lose the game in her second turn. (Note that in this example S is exactly equal to the sum of all girls' numbers.)
10
{10,40}
{20,30}
Returns: 0
In every case, Kaede loses in her first turn because S is equal to the smallest element in her sequence.
25
{6,14}
{7,1}
Returns: 2
178
{25,6,14,100,71,49}
{17,7,1,100,62,43}
Returns: 240192
4
{1,1,1,1}
{1,1,1,1}
Returns: 576
Each of the (N!)^2 ways to permute the two sequences is counted separately, even if different permutations produce the same sequences of numbers.
Submissions are judged against all 51 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrettyLiar with a public method int count(int S, vector<int> kaede, vector<int> kanade) · 51 test cases · 2 s / 256 MB per case