Lista de probleme 3

O suprafață de teren de formă dreptunghiulară este divizată în N fâșii orizontale și M fâșii verticale, de lățimi egale. Se formează astfel N x M zone de formă pătrată, cu latura egală cu o unitate. Astfel, suprafața este reprezentată sub forma unui tablou bidimensional cu N linii și M coloane, în care pentru fiecare zonă este memorat un număr ce reprezintă altitudinea zonei respective. Interesant este că în tablou apar toate valorile 1, 2, …, N•M. Suprafața este destinată turismului. Deoarece spre laturile de Est și Sud ale suprafeței există peisaje de o frumusețe uimitoare, se dorește găsirea unor trasee turistice în care deplasarea să se realizeze cu pași de lungime unitară mergând doar spre Est și spre Sud. O comisie, care trebuie să rezolve această problemă, a stabilit că un traseu este atractiv dacă și numai dacă ultima poziție a traseului are altitudinea mai mare decât prima poziție a traseului. Un traseu poate începe, respectiv se poate încheia, în oricare dintre zonele terenului, cu respectarea condițiilor anterioare. Se cere să se determine numărul maxim Z de zone pe care le poate avea un traseu atractiv.

După ce a primit de la Simonet, profesorul său de studii sociale, tema pentru proiect, tânărului Trevor i-a venit ideea jocului “Pay it forward”. Pentru cei care nu știu acest joc, el constă în ajutarea de către Trevor a oamenilor aflați la ananghie. Aceștia la rândul lor vor ajuta alți oameni și așa mai departe. Fiecare participant (inclusiv Trevor) trebuie să realizeze câte k fapte bune prin care să ajute oamenii. Vârstnicii și tinerii își îndeplinesc în mod diferit această sarcină. Vârstnicii au nevoie de zv zile pentru a introduce în joc o altă persoană, iar tinerii au nevoie de zt zile. Astfel dacă un vârstnic, respectiv un tânăr, intră în joc în ziua i, el va introduce la rândul lui în joc prima persoană în ziua i+zv, respectiv în ziua i+zt tânărul, a doua persoană în ziua i+2*zv, respectiv în ziua i+2*zt tânărul și așa mai departe. Astfel numărul de persoane care participă la joc poate fi diferit în funcție de cum sunt alese persoanele vârstnice și cele tinere. Trevor dorește ca în joc să fie realizate în total cât mai multe fapte bune, dar fiecare participant să aducă în joc maximum (k+1)/2 tineri și maximum (k+1)/2 vârstnici. Participanții pot aduce mai puține persoane de un anumit tip, dar nu au voie să depășească numărul de (k+1)/2 persoane de același tip. Care este numărul fb de fapte bune care mai sunt de realizat, după trecerea a n zile, de către persoanele intrate deja în joc, astfel încât numărul total de fapte bune așteptate (și cele realizate și cele nerealizate) să fie maxim?

Se dă o matrice A cu N linii și M coloane, cu valori cuprinse între 1 și N∙M inclusiv, nu neapărat distincte. O operație constă în selectarea a două linii sau două coloane consecutive și interschimbarea acestora (swap). O matrice yin-yang este o matrice în care A[ i ] [ j ] ≥ A[ i ][ j – 1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N și 2 ≤ j ≤ M și A[ i ][ j ] ≥ A[ i – 1][ j ], pentru orice pereche (i, j) cu 2 ≤ i ≤ N și 1 ≤ j ≤ M.

Să se determine numărul minim de operații necesare pentru a transforma matricea dată într-o matrice yin-yang.