[伯俊]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にコードを移動します.
に答える
ref: https://mountrivers.github.io/boj17297/
F(m)以下に示すように、m文字については、フィボナッチ数列で表すことができる文字列である.
F(m) = F(m - 1) + F(m - 2)
幸いなことに、文字列はMessiとGimossiしか存在しないので、文字列の数自体を予測するのは簡単です.肝心なのは、F(m)上でバイナリを検索するようにF(m)を検索するかどうかを思い出すことです.
スペースは無視します.これらの値は問題の再生値ではありませんが、次の状況を考慮してください.
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])
Reference
この問題について([伯俊]Messi Gimossi), 我々は、より多くの情報をここで見つけました https://velog.io/@naem1023/Messi-Gimossiテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol