Diferente pentru problema/colorfulconflict intre reviziile #7 si #19

Diferente intre titluri:

colorfulconflict
Colorfulconflict

Diferente intre continut:

== 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. Gasiti 3 culori pentru care, oricum as alege doua, ele sa *nu* fie in $_conflict_$.
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_$.
h2. Date de intrare
h2. Date de ieşire
În fişierul de ieşire $colorfulconflict.out$ se afla fie numarul $-1$, in cazul in care nu exista 3 culori cu proprietatea ceruta. Daca exista, se vor afisa cele 3 numere care identifica cele 3 culori gasite.
Î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.
h2. Restricţii
* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i,j~} ≤ 1.000.000$
* Pentru $33%$ din punctaj, $A{~i,j~} ≤ 100$
* Pentru $6%$ din punctaj, $N ≤ 5$
* Pentru $7%$ din punctaj, $N ≤ 5$
* Pentru $11%$ din punctaj, $N ≤ 10$
* Pentru $17%$ din punctaj, $N ≤ 20$
* Pentru $16%$ din punctaj, $N ≤ 20$
* Pentru $24%$ din punctaj, $N ≤ 50$
* Pentru $52%$ din punctaj, $N ≤ 200$
* Pentru $49%$ din punctaj, $N ≤ 200$
h2. Exemplu
table(example). |_. colorfulconflict.in |_. colorfulconflict.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
| 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
|
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") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.