Lista de probleme 2

O suprafaţă dreptunghiulară de înălţime N şi lăţime M unităţi trebuie acoperită perfect (placată) prin utilizarea unor plăci de formă dreptunghiulară de dimensiune 1 x P sau P x 1, unde P este un număr natural nenul. Suprafaţa dată poate fi privită ca un caroiaj cu NxM pătrăţele egale cu unitatea.

O placare corectă a suprafeţei iniţiale se memorează într-un fişier text folosind următoarele convenţii de codificare:

• pe prima linie se precizează dimensiunile N şi M ale suprafeţei;
• o placă dreptunghiulară de laţime P este codificată prin numărul natural P, iar o placă de înalţime P se codifică prin numărul întreg –P;
• convenim ca placa având ambele dimensiuni egale cu unitatea să se codifice cu valoarea 1;
• pe fiecare din cele N linii ale codificării se află câte un şir de valori întregi reprezentând, în ordine de la stânga la dreapta, codurile plăcilor care se găsesc amplasate începând de la respectiva linie;
• codul P strict mai mare ca 1 al unei placi orizontale apare o singură dată pe linia corespunzătoare pe care se află placa, iar codul –P al unei placi verticale va apare o singură dată şi anume pe prima linie de la care placa respectivă este amplasată în jos pe o anumita coloană a suprafeţei;
• dacă pe o anumită linie a suprafeţei nu există astfel de coduri de plăci, atunci pe respectiva linie din fişier este o singură valoare de 0.

Folosind codificarea unei placări a suprafeţei iniţiale, se poate determina imaginea acestei placări sub forma unui tablou bidimensional A, cu N linii şi M coloane, unde Aij = valoarea absolută a codului plăcii care se suprapune peste pătrăţelul de pe linia i şi coloana j.

Cunoscând codificarea unei placări corecte a suprafeţei date să se obţină imaginea acestei placări (matricea de valori corespunzătoare codificării suprafeţei).

Costel are de rezolvat o temă grea la matematică: având la dispoziţie N numere naturale nenule trebuie să aşeze între acestea 2 operaţii de înmulţire şi N-3 operaţii de adunare, astfel încât rezultatul calculelor să fie cel mai mare posibil. Nu este permisă modificarea ordinii numerelor date.

De exemplu, dacă N=5 şi numerele sunt 4, 7, 1, 5, 3, operaţiile pot fi aşezate 4 + 7 * 1 + 5 * 3, 4 * 7 *1 + 5 + 3, e.t.c

Scrieţi un program care să aşeze două operaţii de înmulţire şi N-3 operaţii de adunare între cele N valori date astfel încât valoarea expresiei obţinute să fie maximă.