Colorfulconflict

colorfulconflict

== include(page="template/taskheader" task_id="colorfulconflict") ==

Se da o matrice de $N$ linii si $N$ coloane. Fiecare celula $(i, j)$ contine culoarea $A{~i,j~}$. Se considera $_boundingbox_$-ul unei culori $x$ ca fiind dreptunghiul de arie minima cu laturile paralele cu cele ale matricei care include toate celulele unde se afla culoarea $x$. Se considera ca doua culori $x$ si $y$ se afla in $_conflict_$ daca si numai daca $_boundingbox_$-urile lor se suprapun (au intersectie de arie nenula). Gasiti 3 culori pentru care, oricum as alege doua, ele sa *nu* fie in $_conflict_$.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $colorfulconflict.in$ contine numarul $N$ pe prima linie. Pe urmatoarele $N$ linii se afla cate $N$ numere, culorile $A{~i,j~}$.

Fişierul de intrare $colorfulconflict.in$ ...

h2. Date de ieşire

În fişierul de ieşire $colorfulconflict.out$ se afla, in cazul in care nu exista 3 culori cu proprietatea ceruta, numarul $-1$. In schimb, daca exista, se vor afisa cele 3 numere care identifica cele 3 culori gasite.

În fişierul de ieşire $colorfulconflict.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i,j~} ≤ 1.000.000$
* Pentru $33%$ din punctaj, $A{~i,j~} ≤ 100$
* Pentru $7%$ din punctaj, $N ≤ 5$
* Pentru $11%$ din punctaj, $N ≤ 10$
* Pentru $16%$ din punctaj, $N ≤ 20$
* Pentru $24%$ din punctaj, $N ≤ 50$
* Pentru $49%$ din punctaj, $N ≤ 200$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. colorfulconflict.in |_. colorfulconflict.out |

| 3
1 4 2
5 1 4
2 5 6
| -1
|
| 6
1 2 3 4 5 1
2 1 5 4 3 2
1 7 8 4 1 2
8 7 1 4 3 9
1 1 1 2 2 2
6 6 6 6 6 6
| 9 5 6
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

In primul exemplu nu exista 3 culori astfel incat orice pereche de culori as alege din cele 3, ele sa nu fie in conflict.
 
In al doilea exemplu, solutiile posibile sunt:
 
* $3 6 9$
* $4 6 9$
* $5 7 9$
* $5 6 7$
* $5 8 9$
* $5 6 8$
* $5 6 9$
* $3 7 9$
* $3 6 7$
* $4 7 9$
* $4 6 7$
* $6 7 9$
* $4 8 9$
* $4 6 8$
* $6 8 9$
 
De asemenea, toate permutarile fiecarei solutii sunt corecte, pentru ca *ordinea in care afisam numerele in fisierul de iesire nu este relevanta*.

...

== include(page="template/taskfooter" task_id="colorfulconflict") ==