Crimson Sexy Jalapeños

• 4방향 각각에서 먹을수 있는 줄의 갯수는 그 방향에서 처음 할라피뇨가 나오기 직전까지의 줄수를 세면 된다. 그리고 이값들은 방향들을 어떤 순서로 먹든지 변하지 않는다.
• 결국 4방향의 먹을수 있는 줄들의 수를 구하면, 그 4개의 수를 갖고 하는 님게임과 동일하다. 이제 님게임의 필승전략대로 xor값이 0으로 유지되도록 해주기만 하면 된다.
• xor을 0으로 유지시키기 위해서는 상대가 1줄만 먹으면 나도 1줄만 먹어야 한다. 그러면 남은 줄수의 합이 한턴에 1개씩만 줄어들기 때문에, 줄수의 합만큼의 턴이 걸린다. 총 줄수의 합은 문제의 제한에서는 최대 2*10^4이지만, 인터랙티브 때문인지 시간에 꽤 빠듯하게 돌아간다. 5초 제한에 4272ms 가 걸려서 통과했다
• 놀랍게도 684ms로 통과한 파이썬 코드가 있다. 가장 빠른 cpp코드가 2780ms였는데 그것보다도 훨씬 빠르다. 소스를 읽어보니, xor값이 아닌 다른 기준을 갖고서 돌을 제거해 나가는것 같은데, 이 방법을 쓰면 한번에 더 많은 돌을 제거할 수 있어서 턴수가 줄어들것 같다. 하지만, 한참 분석해봤지만 이 방법은 정당한 풀이가 아닌것 같다. 오류가 있는 방법인것 같은데 그냥 데이터가 약해서 통과된것 같은 느낌이다..

"""Solution code for "BOJ 18174. Crimson Sexy Jalapeños".

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

Tags: [game theory]
"""

import functools
import operator
import sys


def main():
    R, C, K = [int(x) for x in sys.stdin.readline().split()]
    coords = [[int(x) for x in sys.stdin.readline().split()] for _ in range(K)]

    nums = {
        'left': min(c for r, c in coords) - 1,
        'right': C - max(c for r, c in coords),
        'top': min(r for r, c in coords) - 1,
        'bottom': R - max(r for r, c in coords),
    }

    g = functools.reduce(operator.xor, nums.values())
    if g == 0:
        print('pass')
    else:
        direc, num = next(x for x in nums.items() if g ^ x[1] < x[1])
        nums[direc] = g ^ num
        print(direc, num - nums[direc])
    sys.stdout.flush()

    while (line := sys.stdin.readline().rstrip()) != 'yuck!':
        direc, num = line.split()
        g = nums[direc] ^ (nums[direc] - int(num))
        nums[direc] -= int(num)

        direc, num = next(x for x in nums.items() if g ^ x[1] < x[1])
        nums[direc] = g ^ num
        print(direc, num - nums[direc])
        sys.stdout.flush()


if __name__ == '__main__':
    main()