Lista de probleme 3

Dănuț este un om al peșterii foarte ocupat: are de spart n bolovani. Pentru fiecare bolovan i se cunosc numărul de zile z[i] necesare pentru spargerea lui și termenul limită d[i], adică ultima zi la care acesta ar trebui spart. Dănuț știe că cel mai eficient mod de a lucra este să se concentreze pe un singur bolovan în fiecare zi. Dacă începe să lucreze la un anume bolovan, el va lucra la acesta în continuu până când îl sparge, fără să intercaleze zile în care lucrează la alți bolovani, sau zile libere. Dându-se numărul n de bolovani, precum și numărul de zile necesare pentru spargerea fiecărui bolovan și termenul limită la care acesta ar trebui spart, să se determine o planificare a lucrului la cei n bolovani în așa fel încât un număr maxim de bolovani să fie sparți înainte de termen.

Misiunea lui Loid constă în a dinamita piatra de pe unele niveluri pentru a provoca surparea minei și curgerea nisipului spre nivelurile inferioare. El are de îndeplinit m sarcini numerotate de la 1 la m. Acestea sunt de două tipuri:

• 1 t p (dinamitare): Loid trebuie ca, la secunda t, să dinamiteze piatra de pe nivelul p al minei. Pentru orice astfel de sarcină, Loid știe că, la secunda t, nivelul p conține piatră, iar aceasta va fi înlocuită de aer la secunda t+1, după dinamitare.
• 2 t p (întrebare): Pentru a i se testa perspicacitatea, Loid este întrebat ce conține nivelul p al minei la secunda t: aer, nisip sau piatră?

Dându-se n, conținuturile tuturor nivelurilor minei la secunda 0, m și sarcinile care trebuie îndeplinite, să se determine răspunsurile la sarcinile de tip întrebare.

Costel deține un șir p de n pietricele prețioase numerotate de la 1 la n. Deoarece Costel este un om superstițios, el colecționează pietricele doar de anumite tipuri. Tipul unei pietricele este reprezentat de o literă mică a alfabetului englez, iar fiecare tip în parte are o anumită valoare. Într-o zi, Costel s-a decis să distribuie șirul de n pietricele pe k rafturi astfel încât fiecare raft să conțină câte o subsecvență nevidă de pietricele din șirul original, iar la final, fiecare pietricică să se afle pe exact un raft. Definim valoarea unui raft ca fiind suma valorilor pietricelelor de pe acel raft. Fiind dat șirul de n pietricele, să se distribuie pietricelele din șir în k subsecvențe disjuncte astfel încât:
1) Cea mai mare valoare a unui raft să fie maximă.
2) Cea mai mică valoare a unui raft să fie maximă.