Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-04-07 14:34:46.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:pictura.in, pictura.outSursăTiberiu Popoviciu 2011, Clasa a 9-a
AutorPerticas CatalinAdăugată deperticas_catalinperticas catalin perticas_catalin
Timp execuţie pe test0.65 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pictura

Mitruţ s-a apucat de curând de pictat matrici. Fiindcă vrea să vadă cât de pricepuţi sunteţi voi la pictură, el vă pune la dispoziţie o matrice cu N*M căsuţe pictate de el. Fiecare căsuţă are o culoare între 0 şi K. Dacă o căsuţă are culoarea 0, înseamnă că încă nu a fost pictată. Numim o ‘zonă’ de culoare x, o submulţime maximală de căsuţe din matrice cu proprietatea că toate au culoarea x şi există drum între oricare două(trecând prin căsuţe adiacente de acceaşi culoare). Se ştie că toate zonele urmează o linie(de grosime 1) care poate să-şi schimbe direcţia şi să se auto-intersecteze, dar nu se poate dubla(grosimea este 1 peste tot). Pentru mai multă claritate urmăriţi explicaţiile de mai jos.

Zonă validă de culoare x
(2 auto-intersecţtii, 9 schimbări de direcţie)

0 0 0 0 x x x x 0
0 0 x 0 x 0 0 x x
0 x x x x x x 0 x
0 0 x 0 x 0 x 0 x
0 0 x 0 x x x 0 x
0 0 x 0 0 0 0 0 x
0 0 x x x x x x x 

Zonă incorectă de culoare x (nu apare în teste)

0 0 0 0 x 0 0 0 0
0 0 0 0 x x 0 0 0
0 0 0 x x x 0 0 0
0 0 0 x 0 0 0 0 0
0 0 0 x 0 0 0 0 0
0 0 0 x x x 0 0 0
0 0 0 0 0 0 0 0 0

Cerinţă

Să se determine K, numărul de culori folosite, iar pentru fiecare culoare i, determinaţi numărul Zi de zone în care apare, Di de câte ori îşi schimbă direcţia (suma schimbăriilor de direcţie pentru fiecare zonă) şi Ii de câte ori se auto-intersectează (suma numărului de intersecţii pentru fiecare zonă). 

Date de intrare

Fişierul de intrare pictura.in conţine pe prima linie numerele N şi M. Pe fiecare din următoarele N linii se află câte M numere întregi care descriu matricea lui Mitruţ.

Date de ieşire

Fişierul de ieşire pictura.out conţine pe prima linie numărul K de culori folosite. Următoarele K linii cuprind fiecare câte 3 numere. Linia i+1 conţine numerele Zi, Di şi Ii separate prin spaţii. 

Restricţii

  • ... ≤ ... ≤ ...

Exemplu

pictura.inpictura.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?