Cerința problemei

Mihai și Ilinca doresc să se apuce de jucat sah, dar deoarece acesta este încă un pic cam complicat pentru ei, și-au ales un joc oarecum asemănător.

Tabla de joc este formata din $N*M$ căsute. Fiecare căsuță are un cost asociat $C[i][j]$ , un interval $[Min[i][j], Max[i][j]]$ și poate fi colorată în alb sau negru. Jocul este compus din $T$ ture. La fiecare tură $t$ , pentru fiecare casuta $(i, j)$ se procedează după cum urmează:

– Se caută o căsuță $(i', j')$ de culoare opusă căsuței $(i, j)$ și se calculează influența acesteia ca fiind $C[i'][j'] + (|i - i'| + |j - j'|)$ . Dintre toate căsuțele $(i', j')$ se alege cea cu influența cea mai mică, și această influență va deveni scorul căsuței $(i, j)$ , notat cu $S[i][j]$ .

– Dacă $S[i][j]$ este strict mai mic ca $Min[i][j]$ , atunci căsuța $(i, j)$ își schimbă culoarea (din alb în negru și din negru în alb) și costul acestia se mărește cu $1$ .

-Dacă $S[i][j]$ este strict mai mare ca $Max[i][j]$ , atunci căsuța $(i, j)$ își schimbă culoarea, costul acesteia se micșorează cu $1$ și se marcheaza faptul că la tura $t$ , căsuța $(i,j)$ este subapreciata.

La finalul fiecarei ture va trebui sa afișați $4$ numere:

Scorul maxim al unei căsuțe albe
Scorul maxim al unei căsuțe negre
Numărul de casute negre devenite albe în urma acestei ture
Numărul de căsuțe albe devenite negre în urma acestei ture.

La finalul celor $T$ ture va trebui sa afișați, pentru fiecare căsuță $(i, j)$ , turele la care aceasta a fost subapreciata.

Structura datelor de intrare și ieșire

Datele de intrare se citesc de la tastatură. Pe prima linie se află $3$ numere întregi, $N$ , $M$ și $T$ , cu semnificația de mai sus.

Următoarele $N$ linii au fiecare $M$ numere și reprezintă culoarile căsuțelor de joc. Al $j$ -lea element de pe a $i$ -a linie este $0$ , daca culoarea căsuței $(i, j)$ este albă sau $1$ în caz contrar.

Următoarele $N$ linii au fiecare $2 * M$ numere și reprezintă intervalele căsuțelor de joc. Intervalul căsuței $(i, j)$ se află pe a $i$ -a dintre aceste linii, fiind format din elementele $2 * j$ si $2 * j + 1$ .

Datele de ieșire trebuie sa conțina $4 * T$ linii, a $t$ -a dintre aceste linii având $4$ numere întregi:

scorul maxim al unei căsuțe albe
scorul maxim al unei căsuțe negre
numărul de casute negre devenite albe în urma turei de joc $t$ .
numărul de căsuțe albe devenite negre în urma turei de joc $t$ .

După acesta urmează $N * M$ linii ce afișeaza turele la care căsuța $(i, j)$ este subapreciată. O linie este formată din indicii căsuței urmată de turele la care căsuța este subapreciată.

Restricții şi precizări

* $1$ ≤ $N, M,T$ ≤ $50$

* costurile căsuțelor vor fi numere întergi pozitive, mai mici decât $1.000.000.000$

* intervalele căsuțelor de joc vor fi numere întregi, cu valoarea absolută mai mica decât $1.000.000.000$ .

* limită de timp: problema trebuie să ruleze in mai puțin de $30 secunde / test$

*Încercați să lucrați cât mai **modularizat**: Faceți-vă funcții pentru calcularea distanței dintre 2 căsuțe, a influenței unei casuțe, al scorului unei căsuțe, etc.

*Folosiți **alocare dinamică** de memorie acolo unde nu se cunoaște dimensiunea unui vector.

Exemplu
- Date de intrare:

2 3 2
0 1 0
1 1 0
2 1 2
2 0 2
1 2 1 3 0 1
0 0 3 4 2 3

Astfel,

$N = 2, M = 3, T = 2.$

$Culoare[0][0] = ALB ; Culoare[0][1] = NEGRU ; Culoare[0][2] = ALB$

$Culoare[1][0] = NEGRU ; Culoare[1][1] = NEGRU ; Culoare[0][2] = ALB$

$C[0][0] = 2 ; C[0][1] = 1 ; C[0][2] = 2$

$C[1][0] = 2 ; C[1][1] = 0 ; C[2][2] = 2$

$Min[0][0] = 1 ; Max[0][0] = 2 ; Min[0][1] = 1 ; Max[0][1] = 3 ; Min[0][2] = 0 ; Max[0][2] = 1$

$Min[1][0] = 0 ; Max[1][0] = 0 ; Min[1][1] = 3 ; Max[1][1] = 4 ; Min[1][2] = 2 ; Max[1][2] = 3$

Rezultatul rulării problemei pe exemplu ar trebui să fie:

2 3 1 2
2 4 2 1
(0, 0)
(0, 1)
(0, 2) 0 1
(1, 0) 0 1
(1, 1)
(1, 2)

La **prima tură **, scorul căsuțelor este:

2 3 2
3 3 1

După **prima tură**, culorile, respectiv costurile vor fi:

0 1 1
0 1 1

2 1 1
1 0 3

La a **doua tură**, scorul căsuțelor este:

2 3 4
1 2 3

După a **doua tură**, culorile, respectiv costurile vor fi:

0 1 0
1 0 1

2 1 0
0 1 3

Autori: Andrei Pârvu, Emil Racec

Temă 2013

Joc

Cerința problemei

Structura datelor de intrare și ieșire

Restricții şi precizări

Exemplu