Fişierul intrare/ieşire:trecere.in, trecere.outSursăONI 2007, clasa 8
AutorCarmen PopescuAdăugată depeanutzAndrei Homorodean peanutz
Timp execuţie pe test0.175 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trecere

In orasul Ababuribu exista o portiune de sosea speciala de forma dreptunghiulara. Soseaua este formata din m randuri a cate n dale patrate de aceeasi dimensiune. Dalele sunt insa colorate in n culori diferite, codificate prin numere intregi cuprinse intre 1 si n. Se stie ca pentru fiecare culoare exista exact m dale colorate cu aceea culoare. Coordonatele dalelor vor fi date de linia si coloana pe care se gaseste dala, numerotarea randurilor facandu-se de sus in jos incepand cu 1, iar coloanele se numeroteaza de la stanga la dreapta incepand cu 1.

Primarul orasului doreste sa construiasca o trecere de pietoni pe aceasta portiune de sosea. O trecere va fi formata din m dale avand toate aceeasi culoare si aflate vertical una sub alta, de la primul pana la ultimul rand. 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 construita trecerea.
Pentru a construi trecerea, primarul da voie constructorilor sa aleaga culoarea (din cele n disponibile) pe care o va avea trecerea de pietoni precum si coloana pe care se va construi trecerea. De asemenea constructorii au voie sa schimbe intre ele dalele de pe sosea, insa efortul total va trebui sa fie cat mai mic posibil. Efortul schimbarii intre ele a doua dale de coordonatele (x, y) si respectiv (x1,y1) este egal cu |x1 - x| + |y1 - y|, unde prin |a| s-a notat valoarea absoluta a valorii a.

De exemplu pentru soseaua din figura alaturata, cea mai eficienta solutie este construirea unei treceri de culoare 1, pe coloana 6. Efortul construirii acestei sosele este 5. Se vor efectua urmatoarele schimbari: dala (1,6) cu dala (1,7), dala (2,5) cu dala (3,6), dala (3,7) cu dala (4,6).
Daca exista mai multe solutii care implica acelasi efort minim, primarul prefera acea culoare avand cel mai mic cod, iar daca pentru aceasta culoare se pot construi cu acelasi efort minim, mai multe treceri, el va prefera cea mai din stanga trecere.

Cerinta

Fiind date dimensiunile m x n ale soselei si culorile celor m x n dale, se cere sa determinati efortul necesar construirii treceri de pietoni, culoarea pe care o va avea aceasta trecere, precum si coloana pe care va fi construita trecerea.

Date de intrare

Fisierul de intrare trecere.in contine pe prima linie doua numere naturale m si n separate printr-un spatiu, reprezentand numarul de linii respectiv de coloane ale soselei. Urmatoarele m linii ale fisierului vor contine cate n numere naturale cuprinse intre 1 si n (inclusiv) separate prin cate un spatiu, reprezentand culorile dalelor de pe sosea.

Date de iesire

Fisierul de iesire trecere.out va contine pe prima sa linie trei numere intregi a, b si c, separate prin cate un spatiu, avand urmatoarea semnificatie: a - efortul depus pentru construirea trecerii de pietoni, b - culoarea trecerii de pietoni iar c - coloana pe care se construieste trecerea.

Restrictii

  • 1 ≤ n, m ≤ 120
  • Pentru valoarea corecta a efortului depus se acorda 30% din punctaj.

Exemplu

trecere.intrecere.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 sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content