Fișierul intrare/ieșire trecere.in, trecere.out Sursă ONI 2007 clasa a 8-a
Autor Carmen Popescu Adăugată de avatar Isabela_coman Coman Isabela Patricia Isabela_coman
Timp de execuție pe test 1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Trecere (clasa a 8-a)

În orașul Ababuribu există o porțiune de șosea specială de formă dreptunghiulară. Șoseaua este formată din m rânduri a câte n dale pătrate de aceeași dimensiune. Dalele sunt însă colorate în n culori diferite, codificate prin numere întregi cuprinse între 1 și n. Se știe că pentru fiecare culoare există exact m dale colorate cu aceea culoare.
Coordonatele dalelor vor fi date de linia și coloana pe care se găsește dala, numerotarea rândurilor făcându-se de sus în jos începând cu 1, iar coloanele se numerotează de la stânga la dreapta începând cu 1.
Primarul orașului dorește să construiască o trecere de pietoni pe această porțiune de șosea. O trecere va fi formată din m dale având toate aceeași culoare și aflate vertical una sub alta, de la primul până la ultimul rând. Astfel dalele care vor forma trecerea vor avea coordonatele de forma
(1,c), (2,c), (3,c),..., (m,c), unde c este coloana pe care este construită trecerea.
Pentru a construi trecerea, primarul dă voie constructorilor să aleagă culoarea (din cele n disponibile) pe care o va avea trecerea de pietoni precum și coloana pe care se va construi trecerea. De asemenea constructorii au voie să schimbe între ele dalele de pe șosea, însă efortul total va trebui să fie cât mai mic posibil. Efortul schimbării între ele a două dale de coordonatele (x,y) și respectiv (x1,y1) este egal cu |x-x1|+|y-y1|, unde prin |a| s-a notat valoarea absolută a valorii a.
De exemplu pentru șoseaua din figura alăturată, cea mai eficientă soluție este construirea unei treceri de culoare 1, pe coloana 6.

Efortul construirii acestei șosele este 5. Se vor efectua următoarele schimbări: dala (1,6) cu dala (1,7), dala (2,5) cu dala (3,6), dala (3,7) cu dala (4,6).
Dacă există mai multe soluții care implică același efort minim, primarul preferă acea culoare având cel mai mic cod, iar dacă pentru această culoare se pot construi cu același efort minim, mai multe treceri, el va prefera cea mai din stânga trecere.

Cerinta

Fiind date dimensiunile m și n ale șoselei și culorile celor mxn dale, se cere să determinați efortul necesar construirii treceri de pietoni, culoarea pe care o va avea această trecere, precum și coloana pe care va fi construită trecerea.

Date de intrare

Fișierul de intrare trecere.in conține pe prima linie două numere naturale m și n separate printr-un spațiu, reprezentând numărul de linii respectiv de coloane ale șoselei. Următoarele m linii ale fișierului vor conține câte n numere naturale cuprinse între 1 și n (inclusiv) separate prin câte un spațiu, reprezentând culorile dalelor de pe șosea.

Date de ieșire

Fișierul de ieșire trecere.out va conține pe prima sa linie trei numere întregi a, b și c, separate prin câte un spațiu, având următoarea semnificație: a – efortul depus pentru construirea trecerii de pietoni, b – culoarea trecerii de pietoni iar c – coloana pe care se construiește trecerea.

Restricții

1 <= m, n <= 120
Pentru valoarea corectă a efortului depus se acordă 30% din punctaj.

Exemplu

trecere.in trecere.out
4 7
4 3 3 6 3 2 1
6 3 4 6 1 1 5
5 6 2 4 5 4 1
7 2 5 2 7 7 7
5 1 6

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii