Lista de probleme 77

Filtrare

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!

Moș Crăciun pregătește cadourile pentru acest an. El trebuie să dea cadouri identice la n copii. Pentru aceasta, a vizitat m magazine (posibil online) și pentru fiecare magazin a aflat prețul cadoului în acel magazin și numărul de cadouri disponibile în acel magazin.

Determinati suma minimă necesară pentru a cumpăra cele n cadouri. Dacă nu se pot cumpăra cele n cadouri afișați mesajul imposibil.

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.

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 :) )

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ă.

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.

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.

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.

Î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.

Î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.