Diferențe pentru problema/trecere între reviziile #13 si #8

== include(page="template/taskheader" task_id="trecere") ==

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=491
 

Î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.

 
!problema/trecere?trecere.jpg!

!trecere/fi?fi.png!

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.

| 5 1 6
|

h3. Explicație
 
...

== include(page="template/taskfooter" task_id="trecere") ==