Dezvoltăm un smartphone pentru piaţa low-entry. Bugetul alocat platformei hardware este scăzut, implicit şi procesorul este unul ieftin cu putere de calcul mică. Una din cerinţele proiectului este ca agenda telefonică să suporte un număr mare de contacte, iar timpul de căutare al unui contact să fie insesizabil utilizatorului final. Căutarea în agendă se face după prefix – sau, altfel spus, „căutare stil AJAX” – iar lista se actualizează cu noi contacte de pe rețelele sociale.
Cerinţă
Să se realizeze un program care să indexeze lista de contacte pentru o căutare rapidă. Cele două operații posibile sunt de adăugare a unui contact și de aflare a numărului numelor de contacte cu un anumit prefix.
Date de intrare
Programul citeşte din fişierul
agendatelefonica.in. Fişierul conţine un număr
N și
N linii, câte o linie pentru fiecare operație. Pe o linie se găsește un număr, urmat de un spațiu și un șir de caractere. Dacă numărul este
0, numele dat de șirul de caractere este introdus în listă. Dacă numărul este
1, șirul de caractere este prefixul pentru care se vrea numărul de contacte.
Date de ieşire
Programul scrie
K linii (
K este numărul de
1 din fișierul de intrare) în fişierul
agendatelefonica.out, fiecare linie reprezentând numărul de contacte din listă care au respectivul prefix la acel moment.
Restricţii
Cuvintele au până la
100 caractere alfabetice mici.
Cuvintele identice se numără separat.
Numărul de operații nu depășește
10.000.
Unele biblioteci de citire/scriere pot avea funcții lente.
Exemple
agendatelefonica.in | agendatelefonica.out |
7
0 stefan
1 stef
0 ilie
0 mihaela
1 miha
0 mihai
1 miha
| 1
1
2
|