====== 기부왕의 님게임 ======

===== 풀이 =====
  * 주어진 돌더미의 돌 갯수들로부터 승리 여부를 확인하는 것은 기본적인 [[ps:게임 이론#님 게임]]과 동일하다. 돌 개수 3개를 모두 xor한 값이 0이 아니면 이긴다
  * 모든 (x,y,z)에 대해서 가능한 최대 기부 금액을 DP를 이용해서 구하면 된다. 그값을 dp[x][y][z] 에 저장하자.
  * [[ps:게임 이론#제로섬 게임]]이니까, DP식을 세울때에 현재 취하는 액션에서 얻어지는 금액을 고려하지 않아도, 가능한 총 점수를 가지고 식을 세울수 있다. 즉, 현재 내 상태가 (x,y,z)이고 여기에서 어떤 액션을 취해서 다음 상태인 (nx,ny,nz)로 만들수 있다고 한다면, dp[x][y][z] = tot - min(dp[nx][ny][nz]) 가 된다.
  * 주어진 상태가 이길 수 있는 상태라면, 반드시 이길 수 있는 액션을 취해야만 한다. 즉, 모두 xor한 값이 0이 아니라면, 그 값이 0이 되도록 돌을 제거해야 하고, 그러면 가능한 액션은 최대 3가지밖에 없다.
    * dp[x][y][z] = tot - min(dp[y^z][y][z], dp[x][x^z][z], dp[x][y][y^z])
    * 이 경우에는 dp값을 O(1)에 채울수 있다.
  * 주어진 상태가 지는 상태라면, 어떤 액션을 취해도 이길수 없기 때문에, 가능한 모든 액션중에서 기부 금액을 가장 높이는 액션을 취해야 한다.  x+y+z 개의 액션을 고려해야 하므로, dp값을 채우는데에 O(x+y+z) = O(n) 이 걸린다
  * dp 테이블의 크기가 O(n^3) 이고, 한칸을 채우는데에 최악의 경우 (=지는경우) O(n)이 걸리므로 O(n^4)이 걸린다고 생각할수 있지만, 그렇지는 않다. 총 O(n^3)개의 포지션 중에서, 지는 포지션의 수는 O(n^2)개 뿐이기 때문에, 지는 포지션을 O(n)에 채우고 나머지 포지션을 O(1)에 채운다면, 전체 테이블을 채우는데에 O(n^3)이면 충분하다. 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31289. 기부왕의 님게임".

- Problem link: https://www.acmicpc.net/problem/31289
- Solution link: http://www.teferi.net/ps/problems/boj/31289

Tags: [game theory]
"""

import itertools
import sys

MAX = 200
INF = float('inf')


def precompute():
    dp = [[[INF] * (MAX + 1) for _ in range(MAX + 1)] for _ in range(MAX + 1)]
    for x, y, z in itertools.combinations_with_replacement(range(MAX + 1), 3):
        tot = x + y + z
        if x ^ y ^ z == 0:
            dp_cur = tot - min(
                itertools.chain(dp[y][z][:x], dp[z][x][:y], dp[x][y][:z]),
                default=0,
            )
        else:
            take_x = dp[y ^ z][y][z] if y ^ z < x else INF
            take_y = dp[x][x ^ z][z] if x ^ z < y else INF
            take_z = dp[x][y][x ^ y] if x ^ y < z else INF
            dp_cur = tot - min(take_x, take_y, take_z)
        dp[x][y][z] = dp[x][z][y] = dp_cur
        dp[y][x][z] = dp[y][z][x] = dp_cur
        dp[z][x][y] = dp[z][y][x] = dp_cur
    return dp


def main():
    dp = precompute()
    T = int(sys.stdin.readline())
    for _ in range(T):
        x, y, z = [int(x) for x in sys.stdin.readline().split()]
        fp = dp[x][y][z] * 10000
        sp = (x + y + z) * 10000 - fp
        print(fp, sp)


if __name__ == '__main__':
    main()

</dkpr>


{{tag>BOJ ps:problems:boj:플래티넘_4}}