Lista de probleme 13

Se dau două șiruri de numere naturale, cu n, respectiv m elemente, ordonate crescător. Să se determine al treilea șir, care să conţină, în ordine crescătoare, elementele din primele două şiruri.

Mihai s-a decis în sfârșit să compună o melodie. Fără să știe de unde să înceapă, a scris pe o foaie n note muzicale. Fiecare notă muzicală este definită de două valori reprezentând durata și înălțimea acesteia. Dându-se n note sub forma a n perechi de numere, x și y, să se afișeze scorul maxim ce poate fi obținut după gruparea tuturor notelor date în grupuri disjuncte.

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.