[Python] 18689번 Baklawa

 

 

https://www.acmicpc.net/problem/18689

18689번: Baklawa

---

 

23/08/19

 

 

전형적인 스프라그-그런디 문제로, 문제의 상황을 님게임으로 변형시키기만 하면 해결할 수 있는 매우 쉬운 문제이다.

 

---

 

문제 접근 방식:

 

 

문제 정보는 다음과 같이 주어진다.

 

 

게임판의 모습

 

1. 앨리스와 밥이 최적의 방법으로 교대로 게임을 진행함. 선공은 앨리스임.
2. 게임판의 모습은 $x$축으로 $x_i$개, $y$축으로 $y_i$개, $z$축으로 $z_i$개만큼 큐브들이 쌓여있는 모습임.
3. 이 중 몇몇의 큐브들은 "오염된 큐브"임.
4. 자신의 차례 때 전체 큐브를 축에 평행한 방향으로 적절하게 잘라 가져감.
5. 이때, 가져가는 부분에는 오염된 큐브가 있으면 진다.
6. 더 이상 턴을 진행할 수 없으면 짐.

님 게임으로 바꾸는 방법은 다음과 같다.

 

규칙에 따르면 큐브를 잘라서 가져가므로, 오염된 큐브와 오염된 큐브 사이에 있는 멀쩡한 큐브는 못가져간다는 사실을 파악해야 된다.

 

또한 축에 평행하게 자르므로, $x$축 또는 $y$축 또는 $z$축, $3$개의 기준이 존재한다는 사실을 알 수 있다.

 

그렇다면, 입력받은 오염된 큐브들의 $x$좌표의 최대/최소, $y$좌표의 최대/최소, $z$좌표의 최대/최소를 구해서 돌 더미가 $6$개 있는 님 게임으로 바꿀 수 있다.

 

색칠된 큐브가 오염된 블록이라면 왼쪽으로 가져갈 수 있는 기회가 $2$번, 오른쪽으로는 $4$번 존재한다.

 

이를 토대로 구현하면 끝이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 18689번 Baklawa
# 스프라그-그런디 정리, 게임 이론
import sys
input = sys.stdin.readline
L = 1_000_000_000

def solve():
    X, Y, Z, N = map(int, input().rstrip().split())
    if N == 0:
        if (X-1)^(Y-1)^(Z-1) == 0:
            print('Bob')
            return
        else:
            print('Alice')
            return
    else:
        x_M, x_m, y_M, y_m, z_M, z_m = 0, L, 0, L, 0, L
        for _ in range(N):
            x, y, z = map(int, input().rstrip().split())
            if x < x_m: x_m = x
            if x > x_M: x_M = x
            if y < y_m: y_m = y
            if y > y_M: y_M = y
            if z < z_m: z_m = z
            if z > z_M: z_M = z
        x_l, x_r = x_m-1, X-x_M
        y_l, y_r = y_m-1, Y-y_M
        z_l, z_r = z_m-1, Z-z_M
        if x_l^x_r^y_l^y_r^z_l^z_r == 0:
            print('Bob')
            return
        else:
            print('Alice')
            return

for _ in range(int(input())):
    solve()