Page 13 - MATINF Nr.2

Concursul de Informatic˘a Programming Day 13

ˆ
In acest caz, ˆın fis , ierul de ies , ire intellistring.out se vor scrie n linii: pe linia i se scrie un
singur num˘ar natural reprezentˆand lungimea celui mai lung prefix al alfabetului care se g˘ases , te
ca subs , ir ˆın t dup˘a primele i operat , ii.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire intellistring.out se vor scrie n linii, linia i cont , inˆand
mesajul YES dac˘a dup˘a primele i operat , ii stringul t se reg˘ases , te ca subs , ir ˆın s, respectiv NO ˆın
caz contrar.

Restrict , ii s , i preciz˘ari

1. 1 ≤ n, lungimea lui s ≤ 100000
2. O operat , ie pop pe un s , ir t vid las˘a s , irul t nemodificat
3. Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 40% din punctaj

Exemple

intellistring.in intellistring.out Explicat , ie
1 1 p = 1
abcabc 0 Stringul t va ar˘ata dup˘a fiecare operat , ie astfel:
6 1 ”a”, ””, ”a”, ”ab”, ”abb”, ”abbf”.
push a 2 Se iau ˆın considerare subs , irurile de forma:
pop 2 a, ab, abc, abcd, . . . .
push a 2
push b
push b
push f
intellistring.in intellistring.out Explicat , ie
2 YES p = 2
abcabc YES Stringul t va ar˘ata dup˘a fiecare operat , ie astfel:
8 YES ”a”, ””, ”a”, ”aa”, ”aaa”, ”aa”, ”aac”, ”aacb”.
push a YES S , irurile ”aaa” s , i ”aacb” nu se reg˘asesc ˆın s
pop NO (ca subs , iruri); restul se reg˘asesc.
push a YES
push a YES
push a NO
pop
push c
push b

Timp maxim de execut , ie: 0.4 secunde/test.
Memorie total˘a disponibil˘a 16 MB.

Doru Constantin, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti
Solut , ie

Pentru prima cerint , ˘a folosim o stiv˘a. La fiecare operat , ie ”push c” pentru care c completeaz˘a
cel mai lung prefix existent, ad˘aug˘am ˆın stiv˘a perechea format˘a din caracterul c s , i lungimea
curent˘a a string-ului t. Lungimea este folosit˘a pentru a s , ti cˆand un apel de pop va aduce