#4577
Moș Crăciun pregătește deja cadourile pentru acest an. El trebuie să cumpere n
cadouri identice pentru a le duce celor n
copii cuminți. Pentru aceasta, a studiat ofertele a m
magazine (posibil online) și pentru fiecare magazin a aflat numărul de cadouri disponibile în acel magazin.
Cum banii nu sunt o problemă pentru Moș Crăciun, dar vrea ca această activitate să îi ia cât mai puțin timp, Moș Crăciun vrea să afle care este numărul minim de magazine din care poate să cumpere cele n
cadouri necesare.
Ajutați-l pe Moș Crăciun și poate vă veți afla pe lista lui!
#398
De-a lungul principalei străzi din orașul nostru există n
plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește ca plopii să aibă înălțimile în ordine descrescătoare. Pentru aceasta, este posibilă tăierea dintr-un plop a unei bucăți – este o tehnică ecologică, nevătămătoare, în urma căreia plopul nu are de suferit. Plopii nu pot fi înălțați în nici un fel.
Determinați numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.
#4220
Vrei să călătorești n
kilometri din orașul A
în orașul B
cu o mașină care are un rezervor de combustibil care poate asigura un număr de m
kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A
cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare :) )
din folclor
#353
La un festival sunt programate n
spectacole. Pentru fiecare se cunoaște momentul de început și momentul de sfârșit, exprimate prin numere naturale. Un spectator dorește să urmărească cât mai multe spectacole în întregime.
Determinați numărul maxim de spectacole care pot fi urmărite, fără ca acestea să se suprapună.
#2683
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.
Classic Greedy
#2684
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.
Classic Greedy
#341
La magazinul din colț au fost aduse n
cutii, numerotate de la 1
la n
, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oarecare de bomboane din cutia cu număr maxim de bomboane în cea cu număr minim de bomboane.
Determinați un șir minim de operații prin care toate cutiile conțin același număr de bomboane.
#400
Într-un depozit 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.
#401
Î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.
#1340
Î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.