Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WORDBASE - Prosty słownik

Zadaniem programu jest zarządzanie zbiorem słów (słownikiem), poprzez realizację podawanych na wejściu poleceń aktualizacji oraz zapytań.

Wejście i wyjście

Wejście rozpoczyna się od liczby całkowitej t (t<=106 ), określającej liczbę poleceń otrzymywanych przez program. Każda z kolejnych t linii zawiera jedno z następujących poleceń:

  • add word - polecenie dodania do słownika słowa word ,
  • add [n] suffix - jak wyżej, przy czym podana jest tylko końcówka suffix dodawanego słowa; pierwsze n liter słowa (poprzedzających końcówkę) należy przyjąć takich samych, jak w przypadku poprzednio wykonywanej operacji "add",
  • delete word - polecenie usunięcia ze słownika słowa word ,
  • count word1 word2 - żądanie wypisania jednej linii, zawierającej liczbę słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2,
  • list word1 word2 - żądanie wypisania w oddzielnych liniach wszystkich słów ze słownika, które w porządku leksykograficznym występują pomiędzy word1 a word2; wyjście powinno być uporządkowane leksykograficznie (jeżeli word1 <= word2) bądź antyleksykograficznie (jeżeli word1 > word2),
  • show n - polecenie wypisania n-tego w porządku leksykograficznym słowa w słowniku.

Uwagi:

  • Na początku działania programu słownik jest pusty.
  • Słowa należy rozumieć jako łańcuchy znaków o długości między 1 a 107, złożone wyłącznie z czterech możliwych znaków (zgodnie ze zwyczajem przyjmujemy alfabet: {'c', 'g', 't', 'a'}). Porządek leksykograficzny liter jest następujący: 'c' < 'g' < 't' < 'a'.
  • W wymienionych sytuacjach przetwarzane polecenie sterujące nie powinno wpłynąć na zawartość słownika: 1) próba dodania słowa już występującego w słowniku, 2) operacja "add [n] suffix" z błędną (zbyt dużą) wartością parametru n, 3) próba usunięcia słowa nie występującego w słowniku. Polecenie "show n" z błędną (zbyt dużą) wartością parametru n powinno zostać zignorowane.
  • Granice zakresów dla poleceń "count" i "list" należy traktować ,,włącznie".
  • Rozmiary pliku wejściowego oraz poprawnego pliku wyjściowego nie przekraczają 32MB.

Przykład

Wejście:
14
add cta
add [1] tga
add [4] aa
list c a
add [2] aa
add [2] a
count cta ct
delete cta
count c cta
list g ctgaa
delete cta
add c
show 1
count c ctg

Wyjście:
ctga
ctgaaa
cta
3
2
ctaa
ctgaaa
c
1

Dane testowe

Do 4pkt.: wyłącznie polecenia "add word", "list".
Do 6pkt.: wyłącznie polecenia "add word", "delete", "list".
Do 8pkt.: wyłącznie polecenia "add" (dwie wersje), "delete", "list".
Do 10.5pkt.: wszystkie polecenia.


Dodane przez:adrian
Data dodania:2008-03-03
Limit czasu wykonania programu:1s-20s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.