사용자 도구

사이트 도구


ps:problems:boj:31687

Trokut

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

스프라그 그런디

시간복잡도O(T)
인풋사이즈T<=10000
사용한 언어Python 3.11
제출기록31120KB / 52ms
최고기록52ms
해결날짜2024/03/25

풀이

  • 삼각형을 만들면 이기는거니까, 상대에서 삼각형을 만들수 있는 찬스를 주면 지게 된다.
  • 바꿔 말하면, 이미 그어진 선분의 꼭짓점을 포함하는 선분을 그리면 안된다는 말이다. 그러면 상대방이 다음에 삼각형을 완성시킬테니.
  • 결국, 이미 그어진 선분과 교차하지도 않고 터칭하지도 않는 선분만 그릴수 있다는 말이 되고, 그러면 다각형 게임와 동일한 문제가 된다.
  • 결과적으로는 Dawson's Kayle과 같은 문제가 되므로, 주기성을 이용해서 O(1)에 승패를 구할수 있다.

코드

"""Solution code for "BOJ 31687. Trokut".

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

Tags: [game theory]
"""

import sys


# fmt: off
A002187_PERIOD = (8, 1, 1, 2, 0, 3, 1, 1, 0, 3,
                  3, 2, 2, 4, 4, 5, 5, 9, 3, 3,
                  0, 1, 1, 3, 0, 2, 1, 1, 0, 4,
                  5, 3, 7, 4)
A002187_EXCEPTION = {0: 0, 14: 0, 16: 2, 17: 2, 31: 2, 34: 0, 51: 2}
# fmt: on


def grundy_num_of_octal_game(octal_code, n):
    if octal_code == '0.137':  # Dawson's chess
        e, p, n = A002187_EXCEPTION, A002187_PERIOD, n
    elif octal_code == '0.07':  # Dawson's Kayles
        e, p, n = A002187_EXCEPTION, A002187_PERIOD, n - 1
    elif octal_code in {
        '0.4',
        '0.401',
        '0.402',
        '0.403',
        '0.42',
        '0.421',
        '0.422',
        '0.423',
    }:
        e, p, n = A002187_EXCEPTION, A002187_PERIOD, n - 2
    else:
        raise ValueError

    if n <= 0:
        return 0
    return e[n] if n in e else p[n % (len(p))]


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        is_win_pos = grundy_num_of_octal_game('0.07', N) != 0
        print('Lucija' if is_win_pos else 'Ivan')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J M E R Y
 
ps/problems/boj/31687.txt · 마지막으로 수정됨: 2024/03/27 15:10 저자 teferi