Uzdevuma formulējums
Valstī Bananastate drošības dienesti konstatēja, ka izlūku (tautas valodā spiegu), kas darbojas gan valsts iekšienē, gan ārienē, ir palicis pārāk daudz. Viņu visu pārvaldīšana bez datorizētas sistēmas ir palikusi grūta.
Tika nolemts izveidot elektronisko kartotēku. Katram spiegam ir unikāls vārds, ko veido simbolu {a..z, A..Z, 0..9} virkne garumā [1..100]. Lai būtu lielāka konspirācija, katram spiegam ir [1..50] unikālu segvārdu. Segvārdiem tika izmantoti skaitļi robežās [1..10’000’000’000].Viens un tas pats segvārds dažādiem dzīviem spiegiem nevar tikt piešķirts, t.i. katrā brīdī pēc kāda no segvārdiem var noskaidrot konkrēto spiegu. Drošības dienesti nolēma, ka vienlaicīgi nebūs vairāk kā 10’000 spiegu.
Jāizveido elektroniska kartotēka, kas nodrošina spiegu
1. ielikšanu vai segvārdu saraksta papildināšanu (tiek savervēti jauni spiegi vai jau reģistrētam spiegam tiek papildināts segvārdu saraksts),
2. izmešanu (gājis bojā) un
3. meklēšanu (spiega unikālā vārda atrašana, ja zināms kāds no segvārdiem).
Pēc spiega izņemšanas no kartotēkas jaunajiem spiegiem atkal var izmantot segvārdus, kas bija piekārtoti bojā gājušajam spiegam.
Jūsu uzdevums ir noprogrammēt šīs kartotēkas kodolu, kas visas operācijas veic ļoti ātri ( ~O(log(n)) ).
Ieejā ir fails, kas simulē reālās dzīves notikumus jeb komandas kartotēkai. Katra komanda ar parametriem tiek rakstīta savā rindā. Katrā faila rindā var būt pēc patikas daudz lieki tukšumi. Faila lielums nav ierobežots.
Ieejas dati ir korekti saskaņā ar ieejas datu formātu un dotajiem ierobežojumiem.…
