테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Trokut ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

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