[伯俊]Messi Gimossi

https://www.acmicpc.net/problem/17297
に答える
ref: https://mountrivers.github.io/boj17297/
F(m)以下に示すように、m文字については、フィボナッチ数列で表すことができる文字列である.
F(m) = F(m - 1) + F(m - 2)
幸いなことに、文字列はMessiとGimossiしか存在しないので、文字列の数自体を予測するのは簡単です.肝心なのは、F(m)上でバイナリを検索するようにF(m)を検索するかどうかを思い出すことです.
スペースは無視します.これらの値は問題の再生値ではありませんが、次の状況を考慮してください.

N = 100

F(51) = 130

F(50) = 80

F(49) = 50

F(48) = 30

では、F(51)に相当する文字列は、少なくともN文字であるべきである.F(50)は80文字なので.
F(51)=F(50)+F(49)の順で文字列を構成する.この順番が重要です.F(50)の文字数に基づいて、100回の読み直し文字がF(50)にあるか、F(49)にあるかを決定するからである.
ここでF(50)=80であるため、F(50)に100番目の文字列を持つことはできない.
したがって、F(49)で100番目の文字列を検索する手順を繰り返す必要があります.すなわち、100−80=20は、再文字列をF(49)から問題検索に変換する.
F(50)が100より大きい場合は、問題をF(50)から100番目の文字列を検索するように変更します.
空白を考慮して、すぐに空白を探索することもできます.F(50)とF(49)の間のインデックスが100の場合、O(1)は100番目の文字列が空白であることを示す.
コード#コード#
この問題を説明するブログの作成者は、C++で作成し、以下に示すようにPythonにコードを移動します.

import sys
N = int(sys.stdin.readline())

pibo = []
b = 'Messi Gimossi'
q = 5
w = 13
pibo.append(q)
pibo.append(w)

while w < 1073741824:
    e = w
    w = w + q + 1
    q = e
    pibo.append(w)

i = 0
while pibo[i] < N:
    i += 1

'''
String Order
F(M) = F(M-1) + F(M-2)
'''
while i >= 2:
    # Detect space, exit immediately
    if N == pibo[i - 1] + 1:
        N = -1
        break
    # If target is located on F(M - 2)
    elif N > pibo[i - 1]:
        # Decrease counter
        i -= 2
        # Decrease N with F(M - 1)
        N -= pibo[i + 1] + 1
    # If target is located on F(M - 1)
    else:
        i -= 1

if N == -1 or N == 6:
    print('Messi Messi Gimossi')
else:
    print(b[N - 1])