Lista de probleme 193

Sabin merge la colindat de Halloween. Ştiind ca poate colinda la n case, iar la fiecare primeşte g[1], g[2], ..., g[n] bomboane, iar în rucsacul lui încap G bomboane, aflaţi numărul minim de case pe care trebuie să le colinde Sabin pentru a umple ghiozdanul.

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

Gigel a primit cadou n bețe de diferite lungimi. Neștiind ce să facă cu ele, se întreabă dacă poate alege dintre bețele date o parte, astfel încât, lipindu-le, să obțină un băț de lungime S.

Se consideră un șir format din primele N numere naturale nenule. Să se afle numărul de partiții în 2 submulțimi disjuncte cu suma egală care există pentru acest șir.

Se dau n numere naturale reprezentând valorile unor monede și S reprezentând o sumă de bani. Să se afișeze numărul de modalități de a plăti suma cu cele n valori.

După o zi grea de școală, Gigel se joacă GTA (Gigel Troc Auto), jocul său preferat. În acesta trebuie să cumperi mașini de la alți jucători astfel incât să câștigi cât mai mulți bani. Când va intra în joc acesta va avea n cereri de cumpărare (schimb) și b dolari. Jucătorii vând mașini pentru un anumit preț p. Prețul real al acestora este egal cu g. Din păcate, Gigel are un calculator neperformant. Acesta mai are t secunde până când calculatorul său dă crash! Gigel vă roagă să-l ajutați să găsească cea mai bună metodă de a cumpăra automobilele.

Bob deține n boabe, pentru fiecare știindu-se greutatea și prețul. Venind perioada festivalelor, acesta are nevoie de bani. Astfel, s-a gândit că ar trebui să vândă câteva din ele. Acesta va roagă să determinați suma maximă pe care o poate obține, știind că greutățile boabelor vândute trebuie să formeze un subsir strict crescător.

Primesti un vector cu n elemente, trebuie ales un x convenabil astfel incat dupa ce fiecare element al vectorului y devine y xor x maximul din vector sa fie minim. Care este maximul minim?

Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N articole de îmbrăcăminte și încălțăminte cu preturile s1, s2, …, sN lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:
- Puteai economisi mulți bani. Nu ai văzut promoțiile magazinului? Dacă ai fi cumpărat două produse deodată, cel mai ieftin din cele două l-ai fi cumpărat la jumătate de preț. Iar dacă ai fi cumpărat trei produse deodată, ai fi primit pe cel mai ieftin din cele trei gratuit!
Maria și Iulia s-au decis să afle care ar fi fost suma minimă cheltuită pentru a achiziționa în aceeași ordine cele N produse, dar grupând câte un produs, câte două sau câte trei. Pentru că cele două fete nu se descurcă așa de bine la informatică, ele te roagă să le ajuți să determine care este această sumă minimă.

John a pornit într-o drumeție. El se află în orașul 1. Se știe efortul pe care îl depune pentru a străbate fiecare oraș, e[i]. De asemenea, se cunoaște și k[i], cu semnificația că orașul i comunică cu orașele care apartin intervalului [max(1, i - k[i]), min(i + k[i], n)]. Observație : Dacă se află în orașul i, acesta poate merge în orașul j doar dacă i comunică cu j și j comunică cu i. Ajutați-l pe John să determine efortul minim pe care trebuie să-l depună pentru a ajunge în orașul n.