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()
ps/problems/boj/31687.txt · 마지막으로 수정됨: 2024/03/27 15:10 저자 teferi
토론