[Baekjoon] Messi Gimossi

https://www.acmicpc.net/problem/17297

Solution

ref: https://mountrivers.github.io/boj17297/

F(m) is a string expressible as a Fibonacci sequence for the m-th character, as shown below.

F(m) = F(m - 1) + F(m - 2)

Fortunately, since the strings consist only of Messi and Gimossi, predicting the string lengths themselves is easy. The key insight is realizing you can search F(m) in a manner similar to binary search.

Ignoring spaces, and using hypothetical values rather than actual ones, consider this scenario:

• N = 100
• F(51) = 130
• F(50) = 80
• F(49) = 50
• F(48) = 30

Then we can predict that the string corresponding to F(51) contains at least the N-th character, since F(50) is 80 characters.

F(51) = F(50) + F(49) — the order of string composition matters here. Because depending on F(50)‘s character count, the 100th character is either in F(50) or in F(49).

Here F(50) = 80, so the 100th character can’t be in F(50).

So we need to repeat the search for the 100th character in F(49). That is, finding the 100 - 80 = 20th character in F(49).

If F(50) were larger than 100, the problem would change to finding the 100th character in F(50).

When considering spaces, you can detect them immediately. If the index between F(50) and F(49) is 100, then the 100th character is a space — detectable in O(1).

Code

The blogger who explained this problem wrote it in C++. Converted to Python:

1
import sys
2
N = int(sys.stdin.readline())
3

4
pibo = []
5
b = 'Messi Gimossi'
6
q = 5
7
w = 13
8
pibo.append(q)
9
pibo.append(w)
10

11
while w < 1073741824:
12
    e = w
13
    w = w + q + 1
14
    q = e
15
    pibo.append(w)
16

17
i = 0
18
while pibo[i] < N:
19
    i += 1
20

21
'''
22
String Order
23
F(M) = F(M-1) + F(M-2)
24
'''
25
while i >= 2:
26
    # Detect space, exit immediately
27
    if N == pibo[i - 1] + 1:
28
        N = -1
29
        break
30
    # If target is located on F(M - 2)
31
    elif N > pibo[i - 1]:
32
        # Decrease counter
33
        i -= 2
34
        # Decrease N with F(M - 1)
35
        N -= pibo[i + 1] + 1
36
    # If target is located on F(M - 1)
37
    else:
38
        i -= 1
39

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