테페리넷

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

===== 풀이 =====
  * 각 숫자별로 승패 여부를 모두 따로따로 계산할 필요 없이, 숫자의 범위들에 대해서 승패를 계산해주는게 가능하다.
  * 9를 곱해서 n이상으로 만들수 있는 수는 모두 승리포지션이다. w0= ceil(n/9)이라고 하면, [w0, n-1] 범위의 수는 모두 승리포지션.
  * [ceil(w0/2), w0-1] 범위의 수들은 2~9중 어떤값을 곱하든 [w0, n-1] 범위로 들어간다. l0 = ceil(w0/2)이라고 하면, [l0,w0-1] 범위의 수들은 모두 패배 포지션
  * w1 = ceil(l0/9)라고 하면, [w1,l0-1] 범위의 수는 모두 9를 곱하면 [l0,w0-1] 범위로 들어간다. 패배포지션으로 이동시킬수 있는 액션이 있으므로, 이 수들은 모두 승리포지션.
  * 이런식으로 n을 9와 2로 번갈아서 나누어 보면서 w0,l0,w1,l1,w2,l2, ... 을 구해나갈수 있다. 이중에서 시작포지션인 1을 포함하는 범위를 찾으면, 1이 승리포지션인지 패배포지션인지 찾을수 있다. 시간복잡도는 O(logn) 이 된다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 4370. 곱셈 게임".

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

Tags: [game theory]
"""

import sys


def main():
    for line in sys.stdin:
        n = int(line)
        while True:
            n = (n + 8) // 9
            if n <= 1:
                print('Baekjoon wins.')
                break
            n = (n + 1) // 2
            if n <= 1:
                print('Donghyuk wins.')
                break


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}