Fişierul intrare/ieşire:trie.in, trie.outSursăad-hoc
AutorDin FolclorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Trie (clasele 11-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.intrie.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici