사용자 도구

사이트 도구


ps:problems:boj:16443

Bolinhas de Gude

ps
링크acmicpc.net/…
출처BOJ
문제 번호16443
문제명Bolinhas de Gude
레벨플래티넘 2
분류

게임 이론

시간복잡도O(n*m*(n+m) +t)
인풋사이즈n<=100, m<=100, t<=1000
사용한 언어Python 3.11
제출기록34236KB / 124ms
최고기록124ms
해결날짜2023/07/12

풀이

  • 체스 연습와 입출력을 제외하고는 거의 동일한 문제. 풀이는 그쪽 참고

코드

"""Solution code for "BOJ 16443. Bolinhas de Gude".

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

Tags: [game theory]
"""

import functools
import itertools
import operator
import sys

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    l_and_c = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    if any(l == c or l == 0 or c == 0 for l, c in l_and_c):
        print('Y')
        return

    size = max(max(l, c) for l, c in l_and_c) + 1
    grundy = [[0] * size for _ in range(size)]
    for i in range(size):
        grundy[i][i] = INF
    for r in range(1, size):
        for c in range(r + 1, size):
            next_grundy_nums = set()
            for nr in range(1, r):
                next_grundy_nums.add(grundy[nr][c])
            for nc in range(1, c):
                next_grundy_nums.add(grundy[r][nc])
            for nr, nc in zip(range(r - 1, 0, -1), range(c - 1, 0, -1)):
                next_grundy_nums.add(grundy[nr][nc])
            grundy[r][c] = grundy[c][r] = next(
                i for i in itertools.count() if i not in next_grundy_nums
            )

    tot_grundy = functools.reduce(
        operator.xor, (grundy[l][c] for l, c in l_and_c)
    )
    print('Y' if tot_grundy > 0 else 'N')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L U E J P
 
ps/problems/boj/16443.txt · 마지막으로 수정됨: 2023/07/12 15:42 저자 teferi