Fibonacci Game

• 게임규칙을 분석해서 바로 승리전략을 파악하는 것은 사실 쉽지 않고, 그래서 이런 경우에 늘 하듯이 DP를 이용해서 결과를 일일히 계산해보는 것이 정석이다. 이 문제는 N이 작기 때문에, DP를 통해서 답을 계산할수 있다. 하지만, 작은 N값들에 대해서 결과를 나열해보면 규칙성을 찾는것도 어렵지 않다.
  • 수학 게임는 동일한 규칙이지만, N의 범위가 커졌기 때문에 규칙성을 찾아야만 풀수 있다.
• 하지만, 사실 이 게임은 Fibonacci nim이라는 유명한 게임을 그대로 옮겨온 것이다. 그리고 위키피디아 링크에는 이 게임에 대해 전부 분석되어 있다.
  • 처음 주어진 수가 피보나치 수가 아니라면 선공에서 필승법이 존재한다
  • 필승 전략은 주어진 수를 zeckendorf representation로 나타냈을때, 가장 작은 자리의 피보나치수만큼을 제거하는 것이다.
  • 전략을 알고 나면, 이유를 분석하는 것은 가능하다. 내 차례에 가장 작은 자리의 피보나치 수 x를 제거해서 상대에게 넘겨주면, 그 다음 작은 자리의 피보나치 수는 x*2보다 크기때문에, 상대방은 그 다음 작은 자리의 피보나치 수를 제거할 수 없다.
• 결국 문제의 답은, 주어진 수를 zeckendorf representation으로 변환한 뒤에 가장 작은 자리의 피보나치 수를 출력하면 된다. 주어진 수가 피보나치 수라면, -1을 출력한다
• zeckendorf representation은 그리디한 방법으로 O(logn)에 구할수 있다.

"""Solution code for "BOJ 2373. Fibonacci Game".

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

Tags: [game theory]
"""


def zeckendorf_representation(n):
    ret = []
    a, b = 1, 1
    while b <= n:
        a, b = b, a + b
    while n:
        while a > n:
            a, b = b - a, a
        n -= a
        ret.append(a)
    return ret


def main():
    N = int(input())
    zr = zeckendorf_representation(N)
    print('-1' if len(zr) == 1 else zr[-1])


if __name__ == '__main__':
    main()