[Baekjoon] Messi Gimossi

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

Soluzione

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

F(m) e una stringa esprimibile come sequenza di Fibonacci per l’m-esimo carattere, come mostrato sotto.

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

Fortunatamente, dato che le stringhe sono composte solo da Messi e Gimossi, prevedere le lunghezze delle stringhe e semplice. Il punto chiave e rendersi conto che si puo cercare in F(m) in modo simile alla ricerca binaria.

Ignorando gli spazi, e usando valori ipotetici invece di quelli reali, consideriamo questa situazione:

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

Allora possiamo prevedere che la stringa corrispondente a F(51) contiene almeno l’N-esimo carattere, dato che F(50) ha 80 caratteri.

F(51) = F(50) + F(49) — l’ordine di composizione della stringa e importante qui. Perche in base al conteggio dei caratteri di F(50), il 100-esimo carattere si trova in F(50) o in F(49).

Qui F(50) = 80, quindi il 100-esimo carattere non puo essere in F(50).

Quindi bisogna ripetere la ricerca del 100-esimo carattere in F(49). Cioe, trovare il 100 - 80 = 20-esimo carattere in F(49).

Se F(50) fosse stato maggiore di 100, il problema sarebbe diventato trovare il 100-esimo carattere in F(50).

Considerando gli spazi, si possono rilevare immediatamente. Se l’indice tra F(50) e F(49) e 100, allora il 100-esimo carattere e uno spazio — rilevabile in O(1).

Codice

Il blogger che ha spiegato questo problema l’ha scritto in C++. Convertito in 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])