Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-04-18 09:28:20.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cautbin.in, cautbin.outSursăad-hoc
AutorArhiva EducationalaAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.25 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cautare binara

Fie un sir cu N numere naturale ordonate crescator. Se cere sa se raspunda la M intrebari de tipul:
0 x - raspunsul va fi egal cu cea mai mare pozitie pe care se afla elementul cu valoarea x sau -1, daca acesta nu se gaseste in sir
1 x - pozitia in sir pe care se afla elementul cel mai mare mai mic sau egal cu x
2 x - pozitia in sir pe care se afla elementul cel mai mic mai mare sau egal cu x

Date de intrare

Pe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentand numarul de elemente ale 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 linie descriind cate o intrebare de tipul celor precizate mai sus.

Date de iesire

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

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 100 000
  • Elementele sirului se vor incadra pe 31 de biti
  • Elementele sirului sunt numerotate incepand cu 1

Exemplu

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

Indicatii de rezolvare

...

Probleme suplimentare

Probleme care se rezolva cu cautarea binara:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?