Attack on Red Kingdom (Codeforces 1312F)
Tags: Others, games

The Red Kingdom is attacked by the White King and the Black King!The Kingdom is guarded by $$$n$$$ castles, the $$$i$$$-th castle is defended by $$$a_i$$$ soldiers. To conquer the Red Kingdom, the Kings have to eliminate all the defenders. Each day the White King launches an attack on one of the castles. Then, at night, the forces of the Black King attack a castle (possibly the same one). Then the White King attacks a castle, then the Black King, and so on. The first attack is performed by the White King.Each attack must target a castle with at least one alive defender in it. There are three types of attacks:  a mixed attack decreases the number of defenders in the targeted castle by $$$x$$$ (or sets it to $$$0$$$ if there are already less than $$$x$$$ defenders);  an infantry attack decreases the number of defenders in the targeted castle by $$$y$$$ (or sets it to $$$0$$$ if there are already less than $$$y$$$ defenders);  a cavalry attack decreases the number of defenders in the targeted castle by $$$z$$$ (or sets it to $$$0$$$ if there are already less than $$$z$$$ defenders). The mixed attack can be launched at any valid target (at any castle with at least one soldier). However, the infantry attack cannot be launched if the previous attack on the targeted castle had the same type, no matter when and by whom it was launched. The same applies to the cavalry attack. A castle that was not attacked at all can be targeted by any type of attack.The King who launches the last attack will be glorified as the conqueror of the Red Kingdom, so both Kings want to launch the last attack (and they are wise enough to find a strategy that allows them to do it no matter what are the actions of their opponent, if such strategy exists). The White King is leading his first attack, and you are responsible for planning it. Can you calculate the number of possible options for the first attack that allow the White King to launch the last attack? Each option for the first attack is represented by the targeted castle and the type of attack, and two options are different if the targeted castles or the types of attack are different.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.Then, the test cases follow. Each test case is represented by two lines. The first line contains four integers $$$n$$$, $$$x$$$, $$$y$$$ and $$$z$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le x, y, z \le 5$$$). The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).It is guaranteed that the sum of values of $$$n$$$ over all test cases in the input does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print the answer to it: the number of possible options for the first attack of the White King (or $$$0$$$, if the Black King can launch the last attack no matter how the White King acts).


Sample Inputs:
3
2 1 3 4
7 6
1 1 2 3
1
1 1 2 2
3

10
6 5 4 5
2 3 2 3 1 3
1 5 2 3
10
4 4 2 3
8 10 8 5
2 2 1 4
8 5
3 5 3 5
9 2 10
4 5 5 5
2 10 4 2
2 3 1 4
1 10
3 1 5 3
9 8 7
2 5 4 5
8 8
3 5 1 4
5 5 10

Sample Outputs:
2
3
0

0
2
1
2
5
12
5
0
0
2

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
T = int(readline())
Ans = [None] * T
for qu in range(T):
    (N, x, y, z) = map(int, readline().split())
    A = list(map(int, readline().split()))
    ts = 200
    dp = [[0] * 3 for _ in range(ts)]
    table = [[[0] * 4 for _ in range(3)] for _ in range(ts + 8)]
    for hp in range(ts):
        if 0 < hp <= x:
            table[hp][0][0] = 1
            table[hp][1][0] = 1
            table[hp][2][0] = 1
        if 0 < hp <= y:
            table[hp][0][0] = 1
            table[hp][2][0] = 1
        if 0 < hp <= z:
            table[hp][0][0] = 1
            table[hp][1][0] = 1
        for ty in range(3):
            dp[hp][ty] = table[hp][ty].index(0)
        val0 = dp[hp][0]
        val1 = dp[hp][1]
        val2 = dp[hp][2]
        table[hp + x][0][val0] = 1
        table[hp + x][1][val0] = 1
        table[hp + x][2][val0] = 1
        table[hp + y][0][val1] = 1
        table[hp + y][2][val1] = 1
        table[hp + z][0][val2] = 1
        table[hp + z][1][val2] = 1
    cl = None
    for loop in range(10, 61):
        for i in range(loop):
            if dp[ts - 1 - i] != dp[ts - 1 - i - loop]:
                break
        else:
            cl = loop
            break
        continue
    A1 = [None] * N
    for i in range(N):
        a = A[i]
        if a < ts:
            A1[i] = a
        else:
            k = 1 + (a - ts) // cl
            A1[i] = a - k * cl
    xx = 0
    for a in A1:
        xx ^= dp[a][0]
    res = 0
    for a in A1:
        da = dp[a][0]
        if dp[max(0, a - x)][0] ^ da == xx:
            res += 1
        if dp[max(0, a - y)][1] ^ da == xx:
            res += 1
        if dp[max(0, a - z)][2] ^ da == xx:
            res += 1
    Ans[qu] = res
print('\n'.join(map(str, Ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return 3 * u + v

def g(u, v, w):
    return 16 * u + 4 * v + w
t = int(input())
l = 150
ans = []
for _ in range(t):
    (n, x, y, z) = map(int, input().split())
    a = list(map(int, input().split()))
    u = [x, y, z]
    dp = [0] * (3 * (l + 8))
    for i in range(1, l + 1):
        for j in range(3):
            s = set()
            for k in range(3):
                if j ^ k or not max(j, k):
                    s.add(dp[f(i - u[k], k)])
            for k in range(4):
                if not k in s:
                    dp[f(i, j)] = k
                    break
    v = [g(dp[i], dp[i + 1], dp[i + 2]) for i in range(0, 3 * l, 3)]
    v.reverse()
    for i in range(1, l):
        ok = 1
        for j in range(30):
            if v[j] ^ v[i + j]:
                ok = 0
                break
        if ok:
            c = i
            break
    for i in range(n):
        if a[i] <= l:
            continue
        d = (a[i] - l) % c
        a[i] = l - c + d
    b = []
    for i in a:
        s = set()
        for j in range(3):
            s.add(dp[f(i - u[j], j)])
        for j in range(4):
            if not j in s:
                b.append(j)
                break
    (l0, r0) = ([0], [0])
    for i in b:
        l0.append(l0[-1] ^ i)
    for i in b[::-1]:
        r0.append(r0[-1] ^ i)
    r0.reverse()
    ans0 = 0
    for i in range(n):
        for j in range(3):
            if not l0[i] ^ dp[f(a[i] - u[j], j)] ^ r0[i + 1]:
                ans0 += 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
G0 = [[[[0] * 5500 for i in range(6)] for j in range(6)] for k in range(6)]
G1 = [[[[0] * 5500 for i in range(6)] for j in range(6)] for k in range(6)]
G2 = [[[[0] * 5500 for i in range(6)] for j in range(6)] for k in range(6)]
for x in range(1, 6):
    for y in range(1, 6):
        for z in range(1, 6):
            for i in range(1, 5500):
                s = G0[x][y][z][max(0, i - x)]
                t = G1[x][y][z][max(0, i - y)]
                u = G2[x][y][z][max(0, i - z)]
                for j in range(5):
                    if j == s or j == t or j == u:
                        continue
                    else:
                        G0[x][y][z][i] = j
                        break
                for j in range(5):
                    if j == s or j == u:
                        continue
                    else:
                        G1[x][y][z][i] = j
                        break
                for j in range(5):
                    if j == s or j == t:
                        continue
                    else:
                        G2[x][y][z][i] = j
                        break

def lcm(x, y):
    return x * y // math.gcd(x, y)
t = int(input())
for tests in range(t):
    (n, x, y, z) = map(int, input().split())
    B = list(map(int, input().split()))
    A = []
    for a in B:
        if a <= 5400:
            A.append(a)
        else:
            A.append(a % 2520 + 2520)
    XOR = 0
    for a in A:
        XOR ^= G0[x][y][z][a]
    ANS = 0
    for a in A:
        k = XOR ^ G0[x][y][z][a]
        if G0[x][y][z][max(0, a - x)] == k:
            ANS += 1
        if G1[x][y][z][max(0, a - y)] == k:
            ANS += 1
        if G2[x][y][z][max(0, a - z)] == k:
            ANS += 1
    print(ANS)