018 Cautare binara

[•filipb]

Aici puteti discuta despre problema Cautare binara.

[•Robybrasov]

in enunt se cere afisarea numarului cel mai mic mai mare sau egal si cel mai mare mai mic sau egal ca x. asta inseamna ca pentru sirul 5 9 12 12 12 17 23 si x=12 se pot afisa oricare dintre pozitiile 3, 4, 5 pentru ca 12 se afla pe toate acele pozitii, adica 12=12. care pozitie trebuie afisata?

[•gabitzish1]

Din ce am inteles eu, si ce am iplementat de 100 de puncte, in primul caz cand trebuie afisat cel mai mic numar mai mare sau egal cu x, rezultatul e 3, iar in cazul cu cel mai mare numar mai mic sau egal, rezultatul e 5.

[•Robybrasov]

da, am inteles enuntul si mai sus am dat un exemplu de la mine pentru ca intr-un sir crescator o valoare poate sa fie de mai multe ori.
in testele 5 si 7 o valoare apare de doua ori, programul meu afisand pozitia mai mare pentru ultimul caz al problemei, desi teoretic ambele pozitii sunt corecte (enunt: mai mic sau egal/mai mare sau egal)

[•gabitzish1]

Referitor la exemplul tau am raspuns.
Pentru cel mai mic numar mai mare sau egal cu x trebuie afisata pozitia cea mai mica, iar pentru cel mai mare numar mai mare sau egal cu x trebuie pozitia cea mai mare.

[•philip]

La 2 din teste imi iese din timp cu cateva milisecunde... o data la 8 si 10, alta data la 9 si 10:
http://infoarena.ro/job_detail/269188
http://infoarena.ro/job_detail/269185
Cum mai poate fi optimizat?

P.S. Lucrez in pascal.

[Later edit]
Am incercat si cu 3 functii distincte, pt fiecare tip de intrebare. Acum imi iese din timp doar cate un test: 8 sau 10.
http://infoarena.ro/job_detail/269245
http://infoarena.ro/job_detail/269211
Poate ca daca mai incerc sa le evaluez, le prind o data pe toate in timp 
Este vreo sursa in pascal cu 100 de pct?

[editat de moderator] nu posta consecutiv. Editeaza-ti ultimul post.

[•devilkind]

evaluatorul iti opreste programul automat in momentul in care a depasit timpul de executie. Deci desi tie iti arata ca programul tau a depasit timpul de executie cu cateva milisecunde, de fapt acela e timpul la care a fost oprit, nu se stie cat ar mai fi durat pana programul tau s-ar fi terminat.

[•toni2007]

Programul tau intra in 360 de milisecunde pe testul maxim. Incearca sa parsezi citirea, avand in vedere ca o sursa in c intra in 210 milisecunde. In rest sursa imi pare ok ca complexitate .

To admins: Se poate mari limita de timp la 0.35? Avand in vedere ca o sursa cu brut depaseste acest timp, scopul arhivei educationale nefiind acela de a parsa citirea.

[•philip]

evaluatorul iti opreste programul automat in momentul in care a depasit timpul de executie. Deci desi tie iti arata ca programul tau a depasit timpul de executie cu cateva milisecunde, de fapt acela e timpul la care a fost oprit, nu se stie cat ar mai fi durat pana programul tau s-ar fi terminat.

Da, insa uneori intra in timp, alteori nu. De asta tind sa cred ca nu depaseste cu mult.

Programul tau intra in 360 de milisecunde pe testul maxim. Incearca sa parsezi citirea, avand in vedere ca o sursa in c intra in 210 milisecunde. In rest sursa imi pare ok ca complexitate .

To admins: Se poate mari limita de timp la 0.35? Avand in vedere ca o sursa cu brut depaseste acest timp, scopul arhivei educationale nefiind acela de a parsa citirea.

Mi se pare o idee buna. 

[•toni2007]

Ideea e ca depaseste cu aproximativ 60 de ms, Am trimis programul tau dupa ce am modificat limita de timp la 0.5 si iti intra in 0.36 . Dupaia desigur am facut-o la loc 0.3. Daca nu ma crezi te poti uita pe ultima sursa trimisa de mine la cautare binara .

[•philip]

Ideea e ca depaseste cu aproximativ 60 de ms, Am trimis programul tau dupa ce am modificat limita de timp la 0.5 si iti intra in 0.36 . Dupaia desigur am facut-o la loc 0.3. Daca nu ma crezi te poti uita pe ultima sursa trimisa de mine la cautare binara .

Dar timpul variaza destul de tare. Au fost evaluari la care mi-a intrat si testul maxim (http://infoarena.ro/job_detail/269245).
Am parsat cautarea (pentru prima data; sper ca am facut ce trebuia), si acum iese din timp la toate testele dinultima grupa.

[•toni2007]

Din ce am vazut eu, tu parsezi cu buffer de 255 de caractere, cat e string-ul normal. Din ce imi amintesc din pascal, poti declara si string de 1 milion, cat poate fi o linie din fisier. E mai rapid sa citesti tot randul decat bucati din el.

Nu sunt sigur, dar parca mergea ceva de genul:

Cod:

var s : string[1100010];

[•philip]

Nu este in free pascal string cu mai mult de 255 caractere.

[•CezarMocan]

Ba da, este. Se numeste ansistring .

[•philip]

Merge cu ansistring, dar acum am probleme cu limita de memorie. 

L.E. Poate ca ii totusi buna ideea cu ridicarea limitei de timp. 

To admins: Se poate mari limita de timp la 0.35? Avand in vedere ca o sursa cu brut depaseste acest timp, scopul arhivei educationale nefiind acela de a parsa citirea.

[•wefgef]

De ce nu incerci sa citesti intr-un array de char?

[•philip]

De ce ar fi citirea caracter cu caracter mai rapida decat citirea cu numere?

[•pauldb]

To admins: Se poate mari limita de timp la 0.35? Avand in vedere ca o sursa cu brut depaseste acest timp, scopul arhivei educationale nefiind acela de a parsa citirea.

Toate problemele din arhiva educationala vor fi revizuite in timp. Daca vom considera necesar in momentul revizuirii, vom modifica limita de timp.

[•sima_cotizo]

De ce ar fi citirea caracter cu caracter mai rapida decat citirea cu numere?

Nu neaparat citirea char cu char, ci citirea in "bucati" mai mari decat e un int/long. In general bucati de lungime putere a lui 2.

[•philip]

Dar un array de char nu poate fi citit decat caracter cu caracter, asta inseamna "bucati" mai mici decat un numar intreg.

[•sima_cotizo]

Ba poti citi, cu blockread de exemplu: citeste aici. Cineva care stie pascal mai bine ca mine sa ma corecteze/completeze va rog

[•philip]

Trec pe c++

[•peanutz]

Pana la urma cum se acorda punctaj pe urmatoarele 2 cerinte?

1 x - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

Din enunt nu se intelege ca trebuie cea mai mare pozitie posibila(1) sau cea mai mica pozitie posibila(2)... daca se iau in considerare doar astea doua nu e corect..

[•toni2007]

Pentru operatia de tip 1, elementul cel mai mare mai mic decat x, in caz ca sunt mai multe egale (desi nu cred), iei pozitia cea mai mare. La 2 invers, pozitia cea mai mica pe care apare.

[•peanutz]

Nu crezi?

verifica sursa jobului
http://infoarena.ro/job_detail/280859

Chiar cred ca ar fi necesara o modificare in enunt(sau in evaluator).