Lista de probleme 100

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!

Se dă un șir n numere naturale separate prin câte un spațiu.
Se cere să se afișeze numărul de intervale care nu conțin niciun termen al șirului.

Se dă un șir v1, v2, …, vn de numere naturale nenule și de asemenea se dau două numere naturale nenule A și B. Să se determine numărul perechilor (vi , vj) cu i < j și A ≤ vi + vj ≤ B.

Numim factorul-x a 2 numere produsul tuturor factorilor primi comuni și diferiți ai celor 2 numere.

Se dau n numere naturale distincte. Se cere să se afle câți factori-x diferiți pot fi obținuți din toate perechile diferite de numere din șir și să se afișeze aceștia.

Se dau n intervale, să se afișeze care dintre ele includ alte intervale și care sunt incluse într-un interval. Intervalul [a,b] este inclus în intervalul [c,d] dacă c <= a și b <= d (a < b, c < d).

Într-o matrice în care elementele sunt aranjate crescător pe anumite linii şi descrescător pe altele, trebuie găsită linia şi coloana pe care se află un anumit element.

Fermierul Quinto are o livadă plină cu pomi fructiferi. Livada are N rânduri, numerotate de la 1 la N, pe fiecare rând aflându-se câte M pomi fructiferi, numerotaţi de la 1 la M. Livada lui Quinto este una specială, aşa că pentru unii pomi se cunoaşte cantitatea de fructe (exprimată în kg) care poate fi culeasă, iar pentru alţii aceasta poate fi determinată pe baza unei formule. Quinto şi-a propus să recolteze C kg de fructe din pomii aflaţi în livada lui. Acesta foloseşte un utilaj modern pentru culesul fructelor. Utilajul poate fi folosit pe oricare din rândurile livezii, dar poate aduna doar fructele dintr-un şir consecutiv de pomi, începând cu primul pom de pe rândul respectiv, neavând posibilitatea de a culege parţial fructele dintr-un pom. Preocupat de frumuseţea livezii sale, Quinto s-a gândit la restricţii suplimentare pentru recoltarea cantităţii C de fructe. Astfel, el doreşte să adune fructele din pomi de pe maximum R rânduri diferite, pentru ca N-R rânduri să rămână complete. De asemenea, el doreşte să culeagă cu prioritate pomii care au o cantitate cât mai mică de fructe, pentru ca în livadă să rămână cei mai roditori pomi. Quinto şi-a dat seama că este dificil să culeagă fix C kg de fructe, prin urmare este mulţumit şi cu o cantitate mai mare, care respectă celelalte condiţii impuse de el.

Determinaţi cea mai mică valoare X posibilă astfel încât să se poată culege, în condițiile de mai sus, o cantitate de cel puțin C kg de fructe și orice pom din care se culeg fructe să conțină cel mult X kg de fructe.

Sandu a studiat la ora de informatică mai multe aplicații cu vectori de numere naturale, iar acum are de rezolvat o problemă interesantă. Se dă un șir X=(X[1],X[2],…,X[n]) de numere naturale nenule și două numere naturale p1 și p2, unde p1<p2. Sandu trebuie să construiască un nou șir Y=(Y[1],Y[2],…,Y[n*n]) cu n*n elemente obținute din toate produsele de câte două elemente din șirul X (fiecare element din șirul Y este de forma X[i]*X[j], 1<=i, j<=n). Sandu are de calculat două valori naturale d1 și d2 obținute din șirul Y. Valoarea d1 este egală cu diferența maximă posibilă dintre două valori ale șirului Y. Pentru a obține valoarea d2, Sandu trebuie să considere că șirul Y are elementele ordonate descrescător iar d2 va fi diferența dintre valorile aflate pe pozițiile p1 și p2 în șirul ordonat descrescător. Sandu a găsit rapid valorile d1 și d2 și, pentru a le verifica, vă roagă să le determinați și voi.

Dându-se șirul X cu n elemente și valorile p1 și p2, determinați valorile d1 și d2.

N prieteni, numerotaţi de la 1 la N, beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte \( {C}_{i} \) – costul berii lui preferate. Din când în când, câte un prieten, fie el k, cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.

Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. În caz că x este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.

Se consideră un şir cu N numere naturale a[1], a[2], …, a[N]. Asupra unui element a[i] din şir se pot efectua operaţii de incrementare (adunare cu 1: a[i] = a[i] + 1) sau decrementare (scădere cu 1: a[i] = a[i] - 1). Fiecare element din şir poate fi incrementat sau decrementat de oricâte ori. Dat fiind șirul celor N numere naturale, să se determine:
a. numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime;
b. numărul minim de operații (incrementări şi decrementări) ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvență de lungime K formată numai din numere prime.