Fișierul intrare/ieșire | trie.in, trie.out | Sursă | ad-hoc |
---|---|---|---|
Autor | din folclor | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 6144 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Trie (clasele 11 și 12)
Notă: Această problemă este o clonă a problemei Trie de la Infoarena. Diferențele sunt marcate cu bold.
Se dau mai multe operații care gestionează o listă de cuvinte, după cum urmează:
- 0 w – adaugă o apariție a cuvântului w în listă
- 1 w – șterge o apariție a cuvântului w din listă
- 2 w – tipărește numărul de apariții ale cuvântului w în listă
- 3 w – tipărește lungimea celui mai lung prefix comun al lui w cu oricare cuvânt din listă
Date de intrare
Fișierul de intrare trie.in va conține mai multe linii, pe fiecare linie fiind descrierea unei operații, în formatul precizat mai sus.
Date de ieșire
Fișierul de ieșire trie.out va conține, pentru fiecare operație de tip 2 și 3 din fișierul de intrare, răspunsul operației corespunzătoare (în ordinea cerută în fișierul de intrare).
Restricții
- Pentru toate operațiile, cuvântul w este format din maxim 20 de caractere din intervalul ‘a’..‘z’
- Numărul total de operații nu va depasi 100.000
- Operațiile de tip 1 w vor apărea numai dacă w apare cel puțin o dată în lista de cuvinte
- Numărul de șiruri distincte din listă nu va depăși în niciun moment 40.000.
- Am redus limita de memorie la 6 MB pentru a impune compactarea arborelui trie.
- Veți avea nevoie de puțină inspirație pentru a dimensiona corect vectorii. Vestea bună este că porțiunile supradimensionate pe care nu le folosiți nu contează și nu cauzează depășirea limitelor.
Exemplu
trie.in | trie.out |
---|---|
0 lat 0 mare 0 lac 2 la 0 mare 1 lat 0 ma 0 lung 3 latitudine 0 mari 2 mare 0 lat 0 mic 3 latime 2 lac 3 mire |
0 2 2 3 1 2 |