Lista de probleme 5

O colonie de N furnici a început să exploreze sistematic teritoriul din preajma muşuroiului. Furnicile se deplasează doar la dreapta sau în jos. Această parte a teritoriului a fost împătrită în zone dispuse pe linii si coloane sub forma unei matrice cu NX linii şi NY coloane. Furnicile pornesc în explorare una câte una din celula din stânga-sus a matricei. Ele merg alternativ: prima spre dreapta, a doua în jos, a treia din nou la dreapta si tot așa. La fel procedează în fiecare celulă a matricei în care ajung, ghidându-se după feromoni lăsați de celelalte furnici. Astfel prima furnică ce ajunge într-o celulă continuă drumul spre celula din dreapta, a doua furnică care ajunge în aceeași celulă o ia în jos, a treia din nou la dreapta și tot așa. Furnicile merg în acest fel până ies din matrice.
Ce suprafaţă a matricei a rămas neexplorată dacă din muşuroi pornesc N furnici.

Pe când era la grădiniță, Maria era pasionată de colorat folosind cariocile. Într-o zi, doamna educatoare i-a dat 4 carioci (de culori diferite). I-a mai dat Mariei un număr foarte mare de cartonașe pătrate, identice ca dimensiuni. I-a spus acesteia să coloreze laturile (cele patru margini) fiecărui cartonaș, așa încât oricare cartonaș să aibă câte o latură de fiecare dintre cele 4 culori. Așa că, toată dimineața fetița a colorat.
Acum, ajungând în gimnaziu, după ce a găsit cartonașele pe care le-a colorat când era mai mică, s-a gândit la următoarea problemă: poate să așeze a x b cartonașe pe o suprafață dreptunghiulară cu a linii și b coloane, astfel încât să fie îndeplinite condițiile: fiecare dintre cele patru laturi ale zonei dreptunghiulare sa fie colorată cu o singură culoare (fiecare latură cu câte o culoare diferită); cartonașele vecine interioare să aibă latura comună de aceeași culoare.
Pentru mai multe perechi (a,b) date, să se afișeze o posibilitate de a aranja cartonașele sau să se spună că acest lucru nu este posibil.

Se consideră o matrice cu N linii și N coloane care memorează doar cifre. Liniile și coloanele sunt numerotate de la 1 la N. Se consideră de asemenea un vector v de lungime 10, în care v[i] = costul cifrei i (i = 0..9). Trebuie să determinăm un drum de la coloana 1 la coloana N, deci care pornește de la o componentă aflată pe coloana 1 la o componentă de pe coloana N și fiecare pas se face dintr-o poziție (i,j) într-una din pozițiile învecinate pe linie sau coloană, adică (i+1,j), (i-1,j), (i,j+1), (i,j-1), cu condiția să nu iasă din matrice. Costul unui astfel de drum este suma costurilor asociate componentelor prin care trece drumul.
Să se determine numărul minim de cifre distincte prin care trece un drum de la coloana 1 la coloana N. Dacă există mai multe astfel de drumuri, atunci se va determina costul minim al unui astfel de drum.

Într-o țară în curs de dezvoltare, într-un oraș oarecare, parcarea pe care primăria dorește să o construiască are formă dreptunghiulară și o putem codifica folosind o matrice cu L linii (numerotate de la 1 la L) și C coloane (numerotate de la 1 la C). Practic, pentru a o pava pe toată ar fi necesari L x C metri pătrați de dale. Firma care produce dalele și care este agreată de primar construiește dale cu lățimea de un metru și lungime care poate fi mai mare de un metru (dar o valoare întreagă). Firma asamblează dalele în pachete și toate pachetele au exact același conținut (dalele unui pachet pot avea lungimi diferite). Pentru că risipa banului public este în perioada sa de apogeu, primarul hotărăște să cumpere pentru fiecare coloană a parcării câte un pachet de dale și nu va putea folosi la pavarea acelei coloane decât dale din acel pachet. Se mai cunoaște și că în fiecare coloană este plantat exact un copac iar acesta nu va putea fi tăiat. Considerăm că un copac ocupă exact zona corespunzătoare unei dale 1 x 1.
După ce un consilier atrage atenția că e posibil ca structura pachetului achiziționat să nu permită pavarea oricărei coloane, primarul nefiind de acord cu această ipoteză hotărăște să te angajeze ca programator și să îi spui care este numărul de variante distincte de pavare a parcării. La numărarea variantelor trebuie ținut cont că toate dalele dintr-un pachet sunt de culori diferite. Considerăm distincte două modalități de pavare dacă există cel puțin o coloană unde același loc este acoperit de dale de culori diferite.

Se dau două numere naturale P şi Q şi un şir S = S[1], S[2], …, S[N] de numere întregi. Din şirul S trebuie ales un (P,Q)-subşir S[i1], S[i2], …, S[ik] astfel încât k ≥ 2 și P ≤ ij – ij-1 ≤ Q pentru orice j=2..k.
De exemplu, pentru P=2, Q=3 şi S=(2,-3,-7,-8,5,-1), subşirul (2,-3,-8) nu este (2,3)-subşir, dar subşirurile (2,-7,5) și (2,-7,-1) sunt (2,3)-subşiruri.
Pentru orice (P,Q)-subşir X = (S[i11],S[i2], ...,S[ir]), ne interesează valoarea expresiei
e(X) = |S[i1] - S[i2]| + |S[i2] - S[i3]| + ... + |S[ir-1] - S[ir]|
unde cu |a| s-a notat modulul numărului întreg a.
Să se calculeze şi să se afişeze E = max{e(X), X este (P,Q)-subşir al lui S}.