Cautarebinara_aplicatii.pdf

Căutarea binară. Aplicații Se da un sir de numere ordonat crescator cu N elemente, si se cere sa se raspunda la M intrebari de tipul: 0 x - cea mai mare pozitie pe care se afla un element cu valoarea x sau -1 daca aceasta valoare nu se gaseste in sir 1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x 2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala 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 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 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 ≤ 100 000 1 ≤ M ≤ 100 000 Elementele sirului vor fi numere strict pozitive si se vor incadra pe 31 de biti

Exemplu cautbin.in 5 1 3 0 1 2

3 3 3 5

cautbin.out 4 4 2

3 3 3

Rezolvare: a) Prima cerință – față de algoritmul de căutare binară discutat în lecția anterioară se are în vedere faptul că în momentul în care elementul căutat este egal cu elementul din mijloc nu e sigur că ne oprim cu căutarea. În acest caz oprirea căutării (și implicit returnarea poziției celei mai mari din vector) va avea loc dacă: - fie poziția găsită este în extremitatea dreaptă a intervalului (x == dr) sau fie elementul de pe poziția următoare este mai mare decât valoare căutată. Subalgoritm cautare (int st, int dr, int x) //iterativ cat timp (st <= dr) executa m <- st + (dr-st)/2 daca v[m] <= x atunci st  m + 1; altfel dr  m - 1; sf. daca sf. cat timp

m <- st + (dr-st)/2 daca v[m] > x atunci m  m - 1 sf. daca daca v[m] == x atunci returneaza m sf. daca returneaza -1 sf. subalgoritm

Subalgoritm Cautare(st, dr)//recursiv dacă st>dr atunci returneaza -1 altfel m <- st + (dr-st)/2 //mijloc daca x > v[m] atunci Cautare (m + 1, dr)//dreapta altfel daca x < v[m] atunci Cautare (st, m - 1)//st altfel //x == v[m] daca x = dr atunci returneaza m //sunt in extremitatea dreapta altfel daca v[m+1] > x atunci returneaza m; //urmatorul > x altfel Cautare (m + 1, dr)//dreapta sf. daca sf. daca sf. daca sf. daca sf. daca sfârşit subalgoritm

b) A doua cerință Subprogramul va găsi întotdeauna o soluție. - Dacă elementul din mijloc este mai mare decât x, căutarea va continua în subvectorul stâng (st, m1). - În caz contrar (x <= v[m]) vom avea următoarele situații: o m == dr (elemental se găsește în extremitaea dreaptă) return m o în caz contar  dacă v[m+1] > x (următorul element e mai mare decât x) return m  în caz contrar căutarea continuă în subvectorul drept (m+1, dr). c) A treia cerință - este asemănătoare cu a doua.

Numarare triunghiuri Andrei are N betisoare de lungimi nu neaparat diferite. El vrea sa afle in cate moduri poate alege trei betisoare astfel incat sa poata forma cu ele un triunghi.

Cerinta Dandu-se lungimile betisoarelor aflati in cate moduri se pot alege trei dintre ele astfel incat sa se poata forma un triunghi cu ele.

Date de Intrare Pe prima linie a fisierului nrtri.in se afla N, numarul de betisoare. Pe urmatoarea linie se afla N numere separate prin spatii ce reprezinta lungimile betisoarelor.

Date de Iesire Fisierul nrtri.out contine un singur numar ce reprezinta numarul cerut de problema.

Restrictii si precizari    

1 ≤ N ≤ 800 1 ≤ lungimea unui betisor ≤ 30000 se considera triunghiuri si cele care au un unghi de 180 de grade si celelalte doua de 0 grade (2 segmente coliniare se confunda cu al 3-lea) pentru 75 de puncte se garanteaza 1 ≤ N ≤ 150

Exemplu nrtri.in 4 2 3 6 4

nrtri.out 2

Explicatii Singurele triunghiuri care se pot forma sunt alcatuite din urmatoarele betisoare (date prin numarul de ordine): 1, 2, 4 2, 3, 4

Factorial Se da un numar intreg P. Sa se gaseasca cel mai mic numar natural strict pozitiv N pentru care N! are exact P cifre de 0 la sfarsit. Se stie ca N! = 1 * 2 * 3 * .... * (N - 1) * N.

Date de intrare Fisierul fact.in va contine pe prima linie numarul intreg P.

Date de iesire Pe prima linie a fisierului fact.out se va scrie acel numar N care indeplineste condiitle impuse sau -1 daca nu exista un astfel de N.

Restrictii 

0 ≤ P ≤ 108

Exemple fact.in

fact.out

0

1

2

10

10

45

Transport O firma ce produce saltele cu apa are N astfel de saltele intr-un depozit, asezate una peste alta (intr-o stiva). Fiecare saltea este caracterizata prin volumul sau (un numar intreg, exprimat in decimetri cubi). Pentru a le transporta la magazin, in vederea comercializarii, firma va inchiria un camion care va avea o capacitate egala cu C decimetri cubi. Acest camion va trebuie sa efectueze cel mult K transporturi (s-a estimat durata fiecarui transport si s-a ajuns la concluzia ca daca s-ar efectua mai mult de K transporturi, camionul ar ajunge la magazin in afara orelor de aprovizionare, astfel ca saltelele nu ar putea fi comercializate). La fiecare transport, camionul poate fi incarcat cu saltele, cu conditia ca suma volumelor saltelelor incarcate in camion sa nu depaseasca capacitatea camionului. Deoarece saltele sunt asezate intr-o stiva, nu este posibil sa se incarce in camion o saltea decat dupa ce au fost incarcate (si eventual transportate) toate saltelele de deasupra ei. Intrucat costul inchirierii camionului depinde de capacitatea acestuia, firma doreste sa inchirieze un camion cu capacitatea cat mai mica care sa poata transporta toate cele N saltele, efectuand maxim K transporturi.

Date de intrare Pe prima linie a fisierului transport.in se afla numerele intregi N si K (separate printr-un spatiu). Pe fiecare din urmatoarele N linii se afla un numar intreg, reprezentand volumul unei saltele. Prima din aceste N linii contine volumul saltelei din varful stivei, a doua linie contine volumul celei de-a doua saltele, etc.

Date de iesire In fisierul transport.out veti afisa un singur numar intreg, reprezentand capacitatea minima pe care trebuie sa o aiba camionul pentru a putea transporta cele N saltele efectuand maxim K transporturi.

Restrictii si precizari 

1 ≤ N ≤ 16 000

 

1 ≤ K ≤ 16 000 1 ≤ volumul oricarei saltele ≤ 16 000

Exemplu transport.in 6 3 7 3 2 3 1 4

transport.out 8