Lista de probleme 7

Fie şirul tuturor numerelor naturale de la 1 la un număr oarecare N. Considerând asociate câte un semn (+ sau -) fiecărui număr şi adunând toate aceste numere cu semn se obţine o sumă S. Pentru un S dat, găsiţi valoarea minimă N şi asocierea de semne numerelor de la 1 la N pentru a obţine S în condiţiile problemei.

În urma bombardamentelor din 11 septembrie 2001, clădirea Pentagonului a suferit daune la unul din pereții clădirii. Imaginea codificată a peretelui avariat se reprezintă sub forma unei matrice cu m linii și n coloane. Sumele alocate pentru refacerea Pentagonului vor fi donate celor care vor ajuta americanii să refacă această clădire prin plasarea, pe verticală, a unor blocuri de înălțimi k, k=1, …, m, și lățime 1, în locurile avariate. Pentru o structură dată a unui perete din clădirea Pentagonului, determinați numărul minim al blocurilor, de înălțimi k=1, k=2, …, k=m, necesare refacerii clădirii.

Transmiterea şi memorarea informaţiilor necesită diverse sisteme de codificare în vederea utilizării optime a spaţiilor disponibile. Un sistem foarte des întâlnit este acela prin care unei secvenţe de caractere i se asociază un număr. Se consideră cuvintele formate numai cu literele mici ale alfabetului englez a, b, c, …, z (26 de caractere). Din toate aceste cuvinte le considerăm doar pe cele ale căror caractere sunt în ordine strict lexicografică. Dacă se dă un cuvânt, să se precizeze dacă poate fi codificat conform sistemului de codificare. În caz afirmativ să se precizeze codul său.

Se dau N numere reale considerate ca fiind razele a N discuri. Considerăm că așezăm un disc în sistemul xOy dacă îl plasăm la o coordonată x pozitivă suficient de mare, tangent cu axa Ox și deasupra ei, apoi îl împingem spre Oy până când devine tangent cu Oy sau cu primul disc așezat anterior întâlnit. În figura rezultată după așezarea tuturor discurilor în ordinea dată unele dintre ele pot fi considerate dispensabile, pentru că prin eliminarea lor nu se modifică lățimea totală a figurii, adică nici un disc nu se mai poate deplasa spre stânga. Identificați toate discurile dispensabile din figură.

Se consideră o pădure tropicală, reprezentată sub forma unui caroiaj dreptunghiular. Celula din colţul stânga sus al caroiajului are coordonatele (1, 1), iar coordonatele celorlalte celule sunt determinate de linia şi coloana pe care se află. În anumite celule ale caroiajului sunt plasaţi bananieri; o celulă conţine cel mult un bananier. Mai mulţi bananieri care se învecinează pe orizontală sau verticală formează o zonă de bananieri. Într-o astfel de zonă, CEKILI se deplasează uşor, cu agilitatea-i cunoscută, de la un bananier la altul. Determinaţi numărul maxim de bananieri care se poate obţine prin conectarea a exact K zone.

O zonă mlăştinoasă are formă dreptunghiulară, având L linii (numerotate de la 1 la L) şi C coloane (numerotate de la 1 la C). Ea este formată din celule cu latura de o unitate. O parte din acestea reprezintă uscat, iar altele reprezintă apă, uscatul fiind codificat cu 0, iar apa cu 1. Se doreşte să se obţină un drum de pe malul de nord spre cel de sud, trecând doar pe uscat. Deplasarea se poate face cu câte o celulă pe linie, pe coloană, sau pe diagonală. Celulele cu apă pot fi transformate în uscat, paraşutând într-un loc cu apă câte un ponton (o plută) de dimensiunea unei celule. Deoarece paraşutarea este periculoasă, se doreşte să avem un număr minim de paraşutări. Scrieţi un program care determină numărul minim de pontoane şi coordonatele acestora.

Romeo şi Julieta sunt prinşi într-un labirint, dat sub forma unei matrice cu M linii şi N coloane, cu elemente 0 şi 1. Un element 1 reprezintă zid, iar 0 reprezintă spaţiu liber. Romeo şi Julieta se află iniţial în pătratelele (1,1) (Romeo) respectiv (M,N) (Julieta) ale matricei, care conţin 0, se pot deplasa numai pe pătratele care conţin 0 şi nu pot părăsi matricea. Scrieţi un program care va decide care dintre mutări vor fi efectuate de Romeo şi care de Julieta pentru a-i ajuta pe cei doi să ajungă la destinaţii.