Lista de probleme 477

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

Se consideră un graf neorientat conex cu n noduri și n muchii. Să se determine numărul arborilor parțiali ai grafului.

#2884 Rucsac2

Într-un magazin intergalactic sunt n tipuri de obiecte, o infinitate din fiecare; pentru fiecare se cunoaște greutatea G și valoarea V. Un hoț intră în magazin având un rucsac ce poate transporta o greutate maximă GMax. El va fura anumite obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

#2785 galeti

Avem n găleți numerotate de la stânga la dreapta numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți se consideră nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort. Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

#2862 stiva2

Să considerăm o stivă, inițial vidă. Putem efectua următoarele operații:
push(X) – se introduce în stivă litera X (evident, în vârful stivei);
pop – se extrage litera aflată la vârful stivei (operația pop se execută atunci când stiva este nevidă);
top – se afișează litera aflată la vârful stivei (operația top se execută atunci când stiva este nevidă).
O secvență de operații este considerată corectă dacă:
- inițial stiva este vidă;
- se execută o serie de operații push, pop, top, fără a executa pop sau top când stiva este vidă;
- la final stiva este vidă.
Utilizând secvențe corecte de operații, putem afișa diferite șiruri de caractere.
Dat fiind un șir format din litere mari, să se determine numărul minim de operații dintr-o secvență corecte care afișează șirul dat.

Se dă un șir de n cifre. Șirul se împarte în secvențe disjuncte de cifre, fiecare secvență având lungimea cel mult 6. Cu fiecare secvență extrasă se formează numărul corespunzător și apoi se adună doar numerele prime obținute. De exemplu, dacă șirul de cifre este 37237, se pot extrage secvențele disjuncte 3, 72, 37, iar suma numerelor prime este 3 + 37 = 40. O altă modalitate este 3, 7237 care are suma 7240 (deoarece numărul 7237 este prim). Să se determine suma maximă care se poate obține împărțind șirul în secvențe disjuncte de lungimi cel mult 6 și adunând apoi numai numerele prime.

Se dă n și un sir cu n elemente, numere naturale. Folosind metoda HeapSort, să se sorteze crescător șirul și să se afișeze elementele sau, separate prin câte un spațiu.

Spunem că un cuvânt este valid dacă el este format doar cu litere din mulțimea {a,b,c,d} și literele a și b nu sunt alăturate. De exemplu, cuvintele aaaa, acdca sunt valide, dar abbc și baabd nu sunt. Să se determine numărul cuvintelor valide de lungime n. Pentru că acest număr este foarte mare, se va afișa rezultatul modulo 777013.

#2773 fibona

Dorel tocmai a aflat despre existenţa şirului lui Fibonacci: F0=0, F1=1, F2=1, F3=2, F4=3, F5=5,… . Pentru numerele n, k şi p date, Dorel vă roagă să calculaţi suma Fp + Fk+p + F2•k+p + … + Fn•k+p.

Cu n numere naturale, \( a_1, a_2,… , a_n \), se pot calcula următoarele sume:
\( S_1 = a_1 + a_2 + … + a_n \)
\( S_2 = a_1 \cdot a_2 + a_1 \cdot a_3 + … + a_{n-1} \cdot a_n \)
\( S_3 = a_1 \cdot a_2 \cdot a_3 + a_1 \cdot a_2 \cdot a_4 + … + a_{n-2} \cdot a_{n-1} \cdot a_n \)
...
\( S_n = a_1 \cdot a_2 \cdot … \cdot a_n \).

Se dau două numere \(n\) și \(k\) și apoi n numere naturale \( a_1, a_2,… , a_n \). Se cere să se calculeze suma \( S_k \).

Înțelepciunea populară

#2779 cntSQ

Se dă o matrice binară (valori 0 și 1). Să se determine câte pătrate exista cu proprietatea proprietatea că acestea au pe marginea lor doar valori 1.