BitCell

Gimy a fost angajat la o mare firma de telefoane. Acum a primit sarcina sa scrie un program pentru agenda telefonica. Acest program trebuie sa faca niste cautari dupa prefix in agenda.
In agenda telefonului se introduc periodic contacte. Uneori se efectueaza apeluri catre numere de telefon cu 10 cifre.

Cand un utilizator se apuca sa formeze un numar, dupa ce scrie un prefix de lungime k, trebuie sa apara pe ecran numerele tuturor persoanelor existante in agenda pana la acel moment ale caror numere incep cu acel prefix.

Operatia de adaugare a contactelor in agenda este codificata cu 1, iar cea de formare este codificata cu 0.
Gimy vrea sa testeze programul pentru N operatii.

In fisierul de intrare "bitcell22.in" se gaseste pe prima linie un numar natural N.
Pe urmatoarele N linii se gasesc operatiile efectuate de Gimy sub forma:
1 nume numar (in cazul adaugarii de contact in agenda) sau
0 k prefix_de_lungime_k

In fisierul de iesire "bitcell22.out", pentru fiecare operatie de cautare trebuie sa se gaseasca numele persoanelor ale caror numere incep cu prefixul de lungime k dat. (sau -1 daca nu exista)

Exemple:
in


out


Restrictii si precizari:
Numarul de operatii nu depaseste 100.000
Numele nu au mai mult de 15 caractere
Puteti pune intrebari la care sa se poata raspunde cu "DA", "NU". In cazul in care la intrebare nu se poate raspunde cu "DA" / "NU" sau raspunsul la intrebare se gaseste in enunt raspunsul va fi "FARA COMENTARII"

Data start: 18.12.2011 (19:00:00)
Data stop: 25.12.2011 (20:00:00)
Desemnare castigator: 25.12.2011(20:30:00)

Poti adauga niste fisiere cu date de test ceva mai mari ?

Am pus cateva teste aici. Nu iti pot da raspunsurile deoarece sunt teste "oficiale". Timpul asteptat este intre 2 si 10 secunde.

Cum se afişează contactele?
      În ordinea lexicografică a numerelor de telefon -- da/nu
      În ordinea alfabetică a numelor -- da/nu

1) NU
2) NU

contactele se afiseaza in ordinea gasirii lor in lista.

cata45 wrote:1) NU
2) NU

contactele se afiseaza in ordinea gasirii lor in lista.

Adica ordinea in care au fost inserate ?

nomemory wrote:Adica ordinea in care au fost inserate ?

DA

Soltuia se poate se poate downloada de aici (este scrisa in Java (compilatorul e "javac 1.6.0_24"))

Pentru rulare:

(Trebuie sa aiba in aceeasi locatie bitcell22.in)

Output-ul:


PS: Daca pica testele (solutii incorecte, sau ia prea mult timp) poti sa trimiti un mesaj te rog. Poate pana maine apuc sa mai schimb ceva.

Solutia ta pica 7 teste din 100.


Time: 83.159 s
Score: 9.30 p

Hai ca mi-a venit pofta sa particip( dupa ce am avut de-a face cu o compresie/decompresie RLE pentru cineva, o tema),asa ca postez solutia, probabil este " " si nu va da raspunsurile corecte sau va sta pana la anu(la propriu) ca sa rezolve, dar eu m-am chinuit cum am putut mai bine intr-o asa zi de Craciun, nu vad momentan probleme (dar sunt sigur ca sunt,cel putin cea a timpului), asa ca va pe toti si asta e : BAU!

Solutia ta pica 1 test din 100.


Time: 124.011 s
Score: 9.90 p

---

L.E. (-- 25 Dec 2011, 21:02 --)

nomemory
scor: 93
penalizare : 8.3159
scor final: 84.6841


new_luca
scor: 99
penalizare : 12.4011
scor final: 86.5989

FELICITARI new_luca! Te asteptam cu alt concurs.

Functioneaza mai bine decat ma asteptam solutia mea, dar tot sunt curios ce nu o fi mers bine la testul ala.

Mie imi plac foarte mult concursurile astea, imi place sa imi bat capul incercand sa gasesc solutia la o problema, atat ca nu fac asta prea des(ca sa am de unde propune, nu am nici experienta si nici nu stiu cum sa jurizez) si problemele de aici sunt cele mai grele pe care le-am rezolvat vreodata

"Victoria" asta e asa de forma, imi pare rau ca nu participa mai mult lume ca sa vedem solutiile si ce si cum au facut, sa mai castig/castigam experienta.

Catalin de ceva timp incoace vad ca pe tine e toata povara concursurilor si apreciez asta , sper ca nu ti se pare ca e in zadar toata munca, chiar daca poate parea, multumesc.

BAIETI scularea, haideti mai activ cu participatul.

Tinand cont ca nu am experienta necesara ca sa jurizez si nici nu am probleme ca sa propun oricine poate venit cu propuneri de problema pentru concursul numarul 23

Felicitari new_luca , multumim cata45 de problema.
Asteptam o problema pentru "revelion" .

nomemory...daca vrei (si ai timp, si chef) poti propune tu urmatorul concurs (din moment ce new_luca nu poate propune concursul.)
Astept un raspuns de la tine.

^^ Ramasesem putin uimit. La problemele de geometrie am observat ca nu se inghesuie nimeni. Deci nu voi mai propune asa ceva. Insa am crezut ca la problema asta vor participa mai multi.

Ok, ma gandesc maine si propun. Daca nu imi vine nici o idee, va anunt.

^

OK, oficial sunt in criza de idei. Ce e drept nici nu prea am avut timp sa ma gandesc... nu stiu ce concurs sa propun.
Daca are cineva idei, ar fi perfect.

Din lipsa de timp am incetat sa mai particip la concursuri , dar iti pot da o idee . Ce zici de o problema cu grafuri , de exemplu se dau n orase cu drumuriile dintre ele si lungimea lor , sa se gaseasca un drum de lungime minima ce va unii toate cele n orase.

^ Nu stiu daca e o idee buna sa dai grafuri (ar micsora si mai mult numarul de participanti). (Doar o parere)

Pana la urma orice problema e bine venita

Cred ca cel mai bine ar fi sa fie ceva creativ, dar decat nimic ca acum, orice va stoarce creierul concurentilor e numai bun

Cred ca lumea nu prea participa in ultimul timp pentru ca nu ii prea atrage ideea problemelor si nici nu e foarte multa lume in Zona activa ca sa avem de unde populatie potential participanta

Eu unul astept fiecare problema in parte cu nerabdare dar se pare ca sunt printre putinii, unora li s-a luat, multi nu au timp si nici nu isi fac, deh prioritatile vietii..... tot e bine ca are cine sa mai propuna probleme

Mi-a venit o idee, hai sa facem o chestie mai practica: un joc de tip spanzuratoarea. Apoi votam jocul castigator .
Acordam concursului vreo 2 saptamani, sa avem timp sa-l concepem (nu ca ar fi prea complicat, dar timpul bate-l vina).
Putem sa folosim orice limbaj, librarie, etc. Se preteaza si ca un program in consola (grafica sa fie niste ascii-uri).

So ?