Lista de probleme 3

Fie un șir de n numere naturale v[1], v[2], …, v[n], unde v[i] reprezintă al i-lea număr din șir. O subsecvență [x, y] a șirului v (cu 1 ≤ x ≤ y ≤ n) conține toate elementele v[x], v[x+1], ..., v[y - 1], v[y]. Fiind date două numere naturale n și k și un șir v de n numere naturale, scrieți un program care să răspundă la următoarea întrebare: câte subsecvențe conțin simultan cele mai mici k valori distincte din șir?

Robotul Vasile s-a angajat la un depozit de pixuri. Aici pixurile sunt ambalate în cutii. Există N tipuri de cutii; într-o cutie de tipul i (1 ≤ i ≤ N) sunt ambalate exact nr[i] pixuri (nr[1] ≤ nr[2] ≤ ... ≤ nr[N]). În depozit există un număr atât de mare de cutii de fiecare tip încât Vasile poate utiliza oricâte cutii doreşte, de orice tip. Sarcina robotului Vasile este să livreze pixurile comandate de diferite firme de birotică. El nu ştie câte pixuri va avea de livrat la următoarea comandă, dar ştie că vor fi cel mult Vmax pixuri. Ca urmare, pentru a fi eficient, robotul Vasile vrea să îşi pregătească în camera de livrare un număr minim de cutii de pixuri astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax folosind cutiile pregătite, evident, fără a deschide cutiile. Scrieţi un program care citeşte valorile N, nr[1], nr[2], … nr[N] şi Vmax și determină numărul minim de cutii pe care robotul Vasile trebuie să le pregătească în camera de livrare astfel încât să poată livra orice număr de pixuri cuprins între 1 şi Vmax, fără a deschide nicio cutie.

Pentru că se plictisește și este foarte inteligent, Radu l-a rugat pe prietenul lui, savantul Feder, să creeze o activitate care să-i pună mintea la încercare. Savantul Feder a adus N piese dreptunghiulare pe care sunt scrise numere naturale și le-a așezat pe masă în ordinea crescătoare a valorilor scrise pe ele, pe poziții consecutive, una lângă cealaltă. Apoi îi dă lui Radu, una câte una, alte M piese dreptunghiulare, pe care sunt scrise numere naturale, într-o ordine oarecare. Când Radu primește o piesă el trebuie să o așeze în șirul de pe masă pe cea mai mică poziție posibilă, astfel încât piesele din șir să rămână în ordine crescătoare. Evident, șirul de pe masă se modifică pe măsură ce Radu așază piesele în șir. Cunoscând șirul pieselor de pe masă, în ordinea în care sunt așezate, precum și cele M piese pe care le primește succesiv Radu, scrieți un program care să afișeze pentru fiecare dintre cele M piese poziția pe care aceasta este așezată în șir.