Fişierul intrare/ieşire:colorfulconflict.in, colorfulconflict.outSursăAlgoritmiada 2019 Runda PreONI
AutorMihai Calancea, Tamio-Vesa NakajimaAdăugată dealexpetrescuPetrescu Alexandru alexpetrescu
Timp execuţie pe test2 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Colorfulconflict

Se da o matrice de N linii si N coloane. Fiecare celula (i, j) contine culoarea Ai,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.

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 Ai,j.

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.

Restricţii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ Ai,j ≤ 1.000.000
  • Pentru 33% din punctaj, Ai,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

Exemplu

colorfulconflict.incolorfulconflict.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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?