Clasa a IX-a lecția 24

Lectie

Cautare Binara

Sa se precizeze daca o valoare x, se afla sau nu intr-un sir dat. Programul va afisa 1 daca x se afla in sir, sau 0 in caz ca x nu apare in sir.

#include <stdio.h>

int main(){
  int n, i, m, val, st, dr, gasit, mij;
    scanf( "%d", &n );
    for( i = 0; i < n; i++ )
      scanf( "%d", &v[i] );
    scanf( "%d", &val );
    st = 0;
    dr = n - 1;
    gasit = 0;
    while( st <= dr && !gasit ) {
        mij = ( st + dr ) / 2;     // mai sigur ar fi: mij = st + ( dr - st ) / 2;
        if( val == v[mij] )
            gasit = 1;
        else if( val < v[mij] )
            dr = mij - 1;
        else
            st = mij + 1;
    }
    printf( "%d ", gasit );
  }

  return 0;
}

Aplicatii

Cautare Binara

Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x.

#include <stdio.h>
int cautb(int v[], int st, int dr, int val ){

  while( st <= dr  ) {
    int mij = ( st + dr ) / 2;
    if( val == v[mij] )
        return 1;
    else if( val < v[mij] )
        dr = mij - 1;
    else
        st = mij + 1;
  }
  return 0;
}

int main(){
  int n, i, m, val, v[25000];

  scanf( "%d", &n );
  for( i = 0; i < n; i++ )
    scanf( "%d", &v[i] );

  scanf( "%d", &m );
  for( i = 0; i < m; i++ ) {
    scanf( "%d", &val );
    printf( "%d ", cautb( v, 0, n-1, val ) );
  }

  return 0;
}

Pozitia celui mai mic numar > x/ celui mai mare numar < x

Voi deplasa limita stanga cand elementul este mai mic sau egal cu x, astfel ca voi ajunge sa ma pozitionez cu indicele stanga peste primul numar mai mare strict ca x. ( limita dreapta va fi fie un element egal cu x, fie pe un element mai mic ca x )

Similar, daca as dori sa gasesc elementul strict mai mic decat x, voi deplasa indicele dreapta cand elementul curent este mai mare si egal cu x. Astfel ca limita dreapta se va opri pe primul element mai mic decat x. (limita stanga va fi fie un element egal cu x, fie pe un element mai mare ca x)

cb

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y. Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

#include<algorithm>
#include <iostream>
int n, v[2000021];
using namespace std;
// cauta pozitia numarului > x 
int cautb(  int st, int dr, int x ){
    int  mij;
    while( st <= dr ) {
        mij = ( st + dr ) / 2;
        if ( v[mij] <= x )
          st = mij + 1;
        else
          dr = mij - 1;
    }
    return st;
// stanga se opreste pe elementul strict mai mare ca x
// dreapta se opreste pe elementul <=x
}
int main(){

  int x , y,  T;
  cin >> n >> T;
  for( int i = 1 ; i <= n ; i++ )
      cin >> v[i];

  sort( v + 1 , v + n + 1 );

  for( int i = 1 ; i <= T ; i++ ){
      cin >> x >> y;
      // numerele mele sunt numerele dintre :
      // elem strict mai mare ca x-1, deci >= cu x
      // elem strict mai mare ca y 
      cout << cautb( 1, n, y ) - cautb(1, n, x - 1) << "\n";
  }
    return 0;
}

Laborator

Aplicatii - Cautare binara

#2644 clase

Într-o școală sunt n clase, fiecare având un număr diferit de elevi. Școală primește m pachete cu cărți, fiecare cu un număr diferit de cărți. Pentru ca o clasa să primească un pachet, numărul elevilor din acea clasa trebuie să fie egal cu numărul cărților din pachet. Să se determine câte clase primesc un pachet de cărți.

#2276 cb

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y. Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

#2239 pow2

Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule. Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

#661 Triunghiuri1

Se dau n numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.

#2273 ssplit

Se consideră un șir a[1], a[2], …, a[n] de numere naturale nenule. Pentru doi indici 1 ≤ i < j < n, notăm cu X = a[1] + a[2] + ... + a[i], Y = a[i+1] + a[i+2] + ... + a[j] și Z = a[j+1] + a[j+2] + ... + a[n]. Să se determine doi indici i și j astfel încât diferența max(X, Y, Z) - min(X, Y, Z) să fie minimă.

#2443 cb2

Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări. Fiecare interogare este dată de o pereche (x, s): care este indicele maxim p cu proprietatea că a[i] ≤ x, pentru orice i=1..p și în plus a[1] + a[2] + ... + a[p] <= s? Trebuie să răspundeți la fiecare din cele Q întrebări.

#2789 cb3

Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerință

Trebuie să răspundeți la cele Q interogări.

#1594 Maraton

După ce și-a cumpărat biscuiți, Costy, eroul nostru, ajunge acasă și se apucă de teme. Astfel, dă peste următoarea problemă: “La o probă de maraton participă N maratonişti. Ştiind că la secunda 0, un maratonist se află la Xi metri de linia de sosire și aleargă cu o viteză de Yi metri/secundă, să se răspundă la Q întrebări de tipul: - Câți maratonişti au trecut linia de sosire după Qi secunde ? “

#536 Fabrica1

La secția de împachetare a produselor dintr-o fabrică lucrează n muncitori. Fiecare muncitor împachetează același tip de produs, și pentru fiecare se cunoaște timpul necesar pentru împachetarea unui obiect. Să se determine durata minimă de timp în care vor împacheta cei n muncitori cel puțin M obiecte.

#2621 spower2

Un număr natural M se numește număr spower2 dacă poate fi descompus astfel: M=2x+2y, cu x≠y. Exemplu: 6 este un număr spower2 (6=2+4), pe când 8 nu este.

Cerința

Se consideră un șir A de n numere naturale. Pentru fiecare element al șirului Ai să se determine cel mai apropiat număr spower2 mai mare sau egal cu Ai, unde 1≤i≤n.

#2252 Profu

Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

Avem n cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr A[i] reprezentând volumul cutiei i = 1,2...,n. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim k transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă x necesară pentru a efectua cele k transporturi. Numărul x este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!

#2453 Rosii mici

Dan este un mare pasionat al fructelor, printre preferatele sale fiind strugurii şi pepenii. Însă recent şi-a descoperit și pasiunea pentru legume, în special pentru roşii, dar mai ales roşiile mici. Spre norocul lui, grădina bunicului este plină de roşii. Grădina are forma unei matrice cu N linii și M coloane cu elemente numere naturale, nu neapărat distincte, unde fiecare element din matrice reprezintă dimensiunea unei roşii. Matricea are proprietatea că oricare coloană are valorile ordonate crescător de sus în jos, adică de la prima spre ultima linie. Bunicul său îi cere să rezolve Q sarcini. Pentru fiecare sarcină, Dan primeşte un număr natural x şi trebuie să găsească o submatrice de arie maximă care începe de pe linia 1 a matricei care reprezintă grădina şi are toate elementele mai mici sau egale decât x. Pentru determinarea submatricei cerute, Dan are voie să mute toate valorile unei coloane în fața oricărei alte coloane. De asemenea, îi este permis să facă oricâte mutări de tipul acesta. Să se calculeze aria maximă a unei submatrice care respectă specificațiile din enunț, pentru fiecare din cele Q sarcini date de către bunic.

#2454 bsrec

Fie un vector v sortat crescător cu N elemente naturale nenule distincte pe care nu le cunoaştem, dar pe care ne propunem să le determinăm. Având la dispoziţie acest vector v, cu ajutorul următorului algoritm de căutare binară putem răspunde la queryuri de forma: Dându-se un număr X şi un interval [a, b] se cere să se determine cel mai mic element mai mare decât X aflat în intervalul determinat de indicii a şi b, interval din vectorul v. Se cunosc paşii pe care algoritmul de cautare binară i-a urmat pentru diferite valori ale tripletului (X, a, b). Dându-se N (lungimea vectorului), Q (numărul de query-uri apelate) şi cele Q query-uri, să se determine vectorul iniţial. Dacă există mai multe soluţii se va afişa soluţia minim lexicografică. Dacă nu există soluţie se va afişa valoarea -1.

#2455 plaja2

Zizi îşi va petrece concediul în această vară într-o frumoasă staţiune de la Marea Neagră. Acolo va sta N zile. Zilele sunt numerotate de la 1 la N. În fiecare dintre cele N zile de concediu, ea intenţionează să facă plajă un număr cât mai mare de unităţi de timp. Va trebui să ţină seama totuşi de prognoza meteo, care este nefavorabilă în K dintre cele N zile, respectiv în zilele z[1], z[2], …, z[k]. În fiecare dintre aceste K zile va ploua sau va fi prea mult soare, iar Zizi va trebui să-şi limiteze timpii de plajă la cel mult t[1], t[2], …, t[k] unităţi de timp. De asemenea, din motive de confort fizic, Zizi doreşte ca diferenţa în valoare absolută a timpilor de plajă între oricare două zile consecutive să nu depăşească T. Cunoscând zilele z[1], z[2], …, z[k] în care există limitările t[1], t[2], …, t[k] pentru timpul de plajă şi valoarea T, să se determine numărul maxim de unităţi de timp pe care Zizi le poate petrece la plajă într-o singură zi dintre cele N zile de concediu.

#2960 abx

Un număr natural n se numește putere dacă există două numere naturale a,b, a ≥ 1, b ≥ 2 astfel încât n=ab. De exemplu, numerele 32 , 169 , 1 sunt puteri (32=25 , 169=132 , 1=12 ), iar 72 , 2000 și 31 nu sunt puteri. Se citesc numerele naturale N , M și un șir de N numere naturale x1,x2,…,xN din intervalul [1,M].

Pentru fiecare din cele N numere xi determinați câte un număr natural ri din intervalul [1,M], cu proprietatea că ri este o putere și pentru orice altă putere p din intervalul [1,M] este îndeplinită condiția |xi–ri|≤|xi–p|, unde |x| reprezintă valoarea absolută a lui x (modulul). Dacă există două puteri egal depărtate de xi se va alege puterea cea mai mică. De exemplu pentru numărul 26, dintre puterile 25 și 27 va fi ales numărul 25.

#2963 mostenire1

Împăratul cel bătrân vrea să împartă sacii cu galbeni din vistieria palatului celor K feciori ai săi, numerotați de la 1 la K în ordinea vârstei. Feciorul cu numărul 1 este cel mai mare, iar mezinul are numărul K. În vistierie sunt N saci plini cu galbeni, așezați în linie, atât de grei încât nu li se poate schimba ordinea, iar pe fiecare sac este scris numărul de galbeni pe care îi conține. Împăratul îl cheamă pe unul dintre feciori și îi spune: “Fiule, a ta este averea primilor x1 saci!”. Feciorul ia sacii și pleacă fericit. Apoi, împăratul cheamă alt fecior și îi spune: “Fiule, a ta este averea primilor x2 saci dintre cei rămași!”. Și așa mai departe, până ajunge la ultimul fecior chemat, căruia îi dă toți sacii rămași. El nu are o ordine anume în care își cheamă feciorii dar are grijă să cheme fiecare fecior exact o dată. Totodată, pentru a evita certurile între ei, este atent ca fiecare fecior să primească cel puțin un sac cu galbeni, dar să NU primească în total mai mulți galbeni ca un frate mai mare decât el. Cel mai mic dintre feciorii împăratului este și cel mai viteaz, așa că împăratul ar vrea să îi dea lui o sumă de bani cât mai mare, fără a-i supăra pe ceilalți feciori ai săi. Cum ar putea împărți împăratul sacii?