Lista de probleme 5

Se dau N şi M două numere naturale şi o matrice A cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M) având elementele numere întregi în intervalul închis [-30000,30000]. Asupra acestei matrice se pot efectua mai multe operaţii de ştergere a unor linii, de ordonare a elementelor aflate pe anumite linii sau de adăugare a unor noi linii la sfârşitul matricei.

Scrieţi un program care citeşte elementele matricei iniţiale, apoi citeşte un şir de comenzi şi determină matricea rezultată după efectuarea operaţiilor precizate prin comenzile respective în ordinea în care acestea sunt date.

Gazonul unui teren de sport de formă dreptunghiulară este întreţinut cu o maşină de tuns iarbă. Dimensiunea terenului este de m rânduri şi n coloane de parcele pătratice de mărime 1×1 metri. Terenul este împrejmuit cu un gard prevăzut cu două porţi amplasate în două colţuri diagonal opuse ale terenului. Vom considera că poarta unu este amplasată în colţul din stânga-sus al terenului iar poarta doi în coltul din dreapta-jos.

Muncitorul care întreţine gazonul doreşte să facă o lucrare frumoasă şi totodată vrea să elimine şi mersul în gol al aparatului. El urmează întotdeauna acelaşi „algoritm” de parcurgere a terenului: intră pe gazon prin poarta unu şi iese prin poarta doi iar între aceste două porţi el urmează întotdeauna un traseu oblic şerpuit care urmează semidiagonalele terenului astfel încât să nu treacă de două ori prin aceeaşi porţiune. Modul în care este alcătuit acest traseu este ilustrat în exemplul următor pentru un teren de de mărime 5 x 8. Se observă că după ce tunde iarba din prima parcelă el se deplasează întodeauna pe orizontală.

În fiecare unitate de timp va fi tunsă câte o parcelă de mărime 1x1 metri. În figura anterioară, numerele care apar reprezintă unitatea de timp în care muncitorul se tunde iarba din parcela respectivă.

Maşina de tuns iarbă este foarte sensibilă la pietrele aflate accidental în iarbă: dacă lama de tăiere a maşinii loveşte o piatră maşina se strică. Din păcate, în timpul ultimului meci disputat un suporter needucat a aruncat o piatră pe teren. Fără să ştie acest „mic amănunt”, muncitorul s-a apucat de treabă, dar în momentul în care maşina a lovit piatra, el s-a oprit din activitate.

Cunoscând coordonatele pietrei (linie, coloană), calculaţi în a câta unitate de timp s-a întâmplat accidentul.

Pentru scrierea mesajelor soldaţii dintr-o unitate militară folosesc 9 litere mici: a, e, i, o, u, m, n, r, s şi caracterul spaţiu. Aceste litere sunt codificate cu ajutorul cifrelor 1, 2, …, 9 (în ordinea de mai sus), iar pentru caracterul spaţiu se foloseşte cifra 0. Astfel codificarea textului ana are mere se poate realiza prin numărul natural 171018206282.

Pentru a mări gradul de securitate a mesajelor transmise soldaţii relizează o supracodificare, înlocuind fiecare cifră k folosită la codicare cu puterea 2k. Astfel textul anterior se supracodifică astfel: 2128212256416442564.

Să se scrie un program care pentru o supracodificare dată, determină textul iniţial. Dacă există mai multe astfel de texte se vor determina toate.

La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară.

Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.

Se dau L şi C două numere naturale şi o matrice cu L linii şi C coloane având elementele numere întregi. Trebuie alese elemente care să respecte următoarele proprietăţi:

• de pe fiecare linie se alege o secvenţă de elemente aflate pe coloane cu indici consecutivi, începând cu elementul de pe prima coloană;
• pentru orice două linii consecutive, lungimile secvenţelor alese trebuie să difere prin 1 sau să fie egale;
• nu trebuie să existe 3 linii consecutive pentru care lungimile secvenţelor alese să fie egale, sau să fie în ordine strict crescătoare sau strict descrescătoare;

Se cere să se facă o alegere a secvenţelor de pe fiecare linie a matricei respectând restricţiile precizate, astfel încât însumând elementele acestora să se obţină suma maximă posibilă.