BagsOfNumbers
TCO19 Semifinal 2 · 2019-11-14 · by majk
Problem Statement
Alice and Bob have n bags, each containing some, possibly zero, positive integers: ones, twos, threes, and fours. They play a game using these bags. Alice goes first, and then they alternate turns. In one turn, a player first selects exactly one of the bags. Then she or he removes some non-empty subset of numbers whose sum is divisible by four. Whoever is not able to make a move, loses.
The number of ones, twos, threes and fours in bag number i is a[i], b[i], c[i] and d[i], respectively. For each of the 2^n - 1 non-empty subsets of bags, consider the game played with only these bags. Determine how many of these games are won by Alice if they both play optimally.
Constraints
- n will be between 1 and 50, inclusive.
- The arrays a, b, c and d will have exactly n elements each.
- Each element of each array will be an integer between 0 and 1018, inclusive.
2
{13,13}
{12,12}
{25,25}
{9,9}
Returns: 2
When there is only single bag, Alice can win by removing all integers in it (their sum is 148, which is divisible by four). When playing with both bags, Bob can simply mirror Alice's moves to win.
4
{3,4,1,7}
{2,2,6,9}
{1,0,7,7}
{3,2,1,1}
Returns: 15
Regardless of the choice of bags, Alice always wins.
4
{0,18,15,16 }
{3,14,8,18 }
{9,12,16,12 }
{0,10,6,7 }
Returns: 14
When bags 0, 1, and 3 are selected, Bob can force win.
10
{3,0,0,1,44,3,27,26,0,41 }
{0,26,0,1,0,0,6,7,1,9 }
{0,9,1,0,5,0,4,5,0,1 }
{0,0,0,0,1,0,3,2,0,0 }
Returns: 512
10
{27,100,0,2,11,0,1,35,0,13 }
{62,18,0,0,55,1,0,79,1,70 }
{71,35,2,0,74,0,0,86,0,22 }
{96,36,0,0,42,0,0,9,0,46 }
Returns: 768
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BagsOfNumbers with a public method long long wonByAlice(int n, vector<long long> a, vector<long long> b, vector<long long> c, vector<long long> d) · 41 test cases · 2 s / 256 MB per case