Lista de probleme 51

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#1340 Rucsac

Într-un magazin sunt n obiecte; 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, sau porțiuni de obiecte, astfel încât suma greutăților obiectelor furate să nu depășească GMax.

Să se stabilească câștigul maxim pe care îl poate obține hoțul. Câștigul este egal cu suma valorilor obiectelor furate. Câștigul adus de o fracțiune de obiect este direct proporțional cu greutatea fracțiunii.

Într-un depozit foarte mare există un raft cu n+1 spații de depozitare, numerotate de la 1 la n+1. Primele n spatii de depozitare sunt ocupate cu n pachete numerotate cu valori între 1 și n, iar spațiul de depozitare n+1 este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice i, pachetul numerotat cu i să se afle în spațiul de depozitare i. Pentru aceasta se va folosi spațiul de depozitare suplimentar, n+1, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

Se dă un șir de n numere naturale. Să se determine numărul minim de subșiruri strict crescătoare în care se poate partiționa șirul.

#1262 subsecv

Se dau n numere naturale. Să se găsească o subsecvență, astfel încât suma elementelor din această subsecvență să fie divizibilă cu n.

#950 Cerc3

Se consideră pe axa Ox din plan n puncte distincte reprezentând centrele a n cercuri numerotate cu numerele distincte de la 1 la n. Pentru fiecare cerc k se cunosc abscisa xk a centrului său şi raza sa rk.

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Olimpiada de Informatică, etapa pe sector, Bucureşti, 2011

Gigel este un cântăreț începător. El știe deja să cânte n piese, și pentru fiecare piesă se cunoaște durata, exprimată în minute și secunde. Gigel va participa la o emisiune de televiziune, unde va putea cânta timp de T secunde. El vrea să cânte cât mai multe piese, pentru a-și demonstra talentul deosebit.

Ajutați-l să aleagă piesele pentru emisiune, și vă va răsplăti cu un autograf.

#556 Flici

Un flic este o creatură pufoasă de dimensiunea unui hamster, având trei ochi și o blană colorată. De la naștere, fiecărui flic îi place în mod deosebit un anumit număr.

Hobby-ul lor este să intre în cutii, iar în lumea flicilor, pe fiecare cutie este inscripționat un număr. Flicii sunt pretențioși și nu vor alege orice cutie. În mod ideal, ar alege cutia pentru care numărul inscripționat este cel mai apropiat de numărul lor favorit, dar pentru că flicii sunt altruiști, vor alege cutiile astfel încât ceilalți flici să nu se supere prea tare.

Astăzi s-a format un grup de n flici, fiecare cu un număr favorit, care au la dispoziție n cutii, fiecare având inscripționat un număr. Sarcina ta este să stabilești pentru fiecare flic în ce cutie va intra, astfel încât suma modulelor diferențelor dintre numărul favorit a flicului și cel inscripționat pe cutia în care intră acesta să fie minimă.

Să se determine o modalitate de parcurgere a unei tablei de către un cal care se deplasează în maniera specifică piesei de șah, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie.

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere întregi. Determinaţi cea mai mare sumă a n elemente din matrice, adunând câte un element de pe fiecare linie a matricei.

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere întregi. Determinaţi cea mai mică sumă a n elemente din matrice, obținută adunând câte un element de pe fiecare coloană a matricei.