Lista de probleme 4

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ă.