[伯俊]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])