Lista de probleme 3

Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli:

• un element egal cu 1 indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0 indică absența ei;
• linia 1 și linia N conțin numai valori egale cu 1, pentru că marginea de sus și cea de jos a plăcii este intactă;
• din orice element egal cu 1, situat în interiorul matricei, se poate ajunge pe linia 1 sau pe linia N sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1;
• există cel puțin o coloană stabilă (formată numai din elemente egale cu 1).

Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.

Să se determine înălțimea minimă Hmin pe care o poate avea placa ștergând cel mult K coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin.

Se consideră un șir de N numere naturale, notate x 1, x 2, x 3,…, x N. Definim pentru orice pereche de indici i, j, 1 ≤ i ≤ j ≤ N, distanța între elementele x i și x j ca fiind egală cu j – i.

Acest șir va fi codificat după următoarele reguli:

• fiecare element din șir este înlocuit cu indicele celui mai apropiat element din șir (cel față de care distanța este minimă) strict mai mare decât el;
• dacă pentru un element din șir există două elemente care respectă regula de mai sus, atunci el va fi înlocuit cu indicele mai mare, adică al elementului strict mai mare decât el, aflat în dreapta lui;
• elementele de valoare maximă din șir vor fi înlocuite cu -1.

Scrieți un program care codifică un șir de N valori, după regulile descrise.

Pe vremea maurilor, transmiterea unor mesaje codificate între două persoane se făcea folosind un cifru numit nod. Cele două persoane alegeau în secret o poveste. Aceasta era scrisă într-o carte folosind litere mici și mari ale alfabetului englez, pe P pagini, numerotate de la 1 la P, fiecare conținând exact R rânduri, numerotate în cadrul fiecărei pagini de la 1 la R, iar fiecare rând fiind format din exact C cuvinte, numerotate în cadrul fiecărui rând de la 1 la C.

Un cuvânt al mesajului de transmis era codificat prin poziția sa în povestea aleasă de cei doi, folosind trei numere scrise cu cifre romane, ce indicau în ordine: numărul paginii, numărul rândului în cadrul paginii, respectiv al cuvântului în cadrul rândului.
Mesajul astfel codificat era scris pe trei linii. Pe prima linie erau scrise numerele paginilor, pe a doua linie numerele rândurilor, iar pe a treia linie erau scrise numerele de ordine ale cuvintelor.

Presupunem că mesajul este format din primul cuvânt de pe al cincilea rând al celei de a doua pagini și din al patrulea cuvânt de pe rândul al doilea al primei pagini. Mesajul putea fi transmis pe trei linii în modul următor:

• II I (numerele paginilor)
• V II (numerele rândurilor)
• I IV (numerele cuvintelor)

Cifrele romane sunt scrise cu majusculele M, D, C, L, X, V, I, iar valorile corespunzătoare lor sunt în ordine: 1000, 500, 100, 50, 10, 5, 1. Valoarea unui număr scris cu cifre romane se calculează parcurgând de la stânga la dreapta cifrele numărului astfel:

• cifra curentă se adună la valoarea obținută până în acel moment, dacă cifra următoare este mai mică sau egală cu ea;
• cifra curentă se scade din valoarea obținută până în acel moment, dacă cifra următoare este mai mare decât ea;
• ultima cifră se adună întotdeauna la valoarea obținută până în acel moment.

De exemplu pentru numărul MCDXLVI scris cu cifre romane, se obține valoarea 1446 în sistem zecimal, astfel: 1000-100+500-10+50+5+1, iar pentru numărul XXI scris cu cifre romane se obține valoarea 21 în sistemul zecimal astfel: 10+10+1.

Cunoscându-se textul poveștii ales de cei doi și mesajul codificat de ei scrieți un program care rezolvă următoarele două cerințe:

a) Rescrie mesajul codificat folosind scrierea cu cifre din sistemul zecimal.
b) Afișează toate cuvintele mesajului decodificat în ordinea în care acestea apar în poveste.