Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-05-07 20:08:51.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:
Invalid task id
.in,
Invalid task id
.out
Sursă
Invalid task id
Autor
Invalid task id
Adăugată de
Invalid task id
Timp execuţie pe test
Invalid task id
sec
Limită de memorie
Invalid task id
kbytes
Scorul tău
Invalid task id
Dificultate
Invalid task id
Invalid task id

Vezi solutiile trimise | Statistici

Invalid task id

Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul:
0 x - pozitia cea mai mare pe care se afla elementul cu valoarea x sau -1 daca nu se gaseste in sir
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

Date de intrare

Pe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentand numarul de elemente alea sirului. Pe urmatoarea linie se gasesc N numere reprezentand elementele sirului. Linia a treia contine numarul M reprezentand numarul de intrebari. Apoi urmeaza M linii, fiecare cu unul dintre cele 3 tipuri de intrebari.

Date de iesire

In fisierul de iesire cautbin.out se vor afisa M linii reprezentand raspunsul la cele M intrebari.

Restrictii

  • 1 ≤ N ≤ 100000
  • 1 ≤ M ≤ 100000
  • Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti

Exemplu

cautbin.incautbin.out
5
1 3 5 8 15
3
0 3
1 2
2 7
2
1
4

Indicatii de rezolvare

O rezolvare avand complexitatea O(N*M) obtine 40 de puncte si se poate gasi aici.
0 rezolvare folosind cautarea binara, in varianta clasica, are complexitatea 0(Mlog2N) si obtine 100 de puncte. Sursa se gaseste aici. De asemenea, o solutie cu aceeasi complexitate teoretica dar mai rapida in practica foloseste cautarea binara pe biti, despre care puteti afla mai multe in articolul Multe "smenuri" de programare in C/C++... si nu numai!. O sursa care se bazeaza pe ideea prezentata in articol se gaseste 'aici':?.
Un alt articol foarte bun despre cautarea binara si aplicatii ale acesteia puteti gasi pe pe topcoder.

Probleme suplimentare

Probleme care se rezolva folosind cautarea binara:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?