stalpi3

Stalpi3

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

Între doi stâlpi verticali aflaţi pe malurile unui râu (de o parte şi de alta a râului) se află  legate două cabluri bine întinse, paralele cu solul, având distanţa dintre ele egală cu $d$ centimetri. Cablurile sunt folosite pentru traversarea râului în caz de inundaţii. Stâlpii sunt notaţi cu A şi B, iar cablurile cu 1 şi 2 ca în figura de mai jos. Pe cabluri există desenate câte $n$ puncte colorate cu diverse culori, culorile fiind codificate prin numerele 1, 2, 3,..., $k$. Poziţia punctelor pe fiecare cablu este dată prin distanţa faţă de stâlpul A pentru fiecare punct. Punctele de pe fiecare cablu sunt numerotate cu 1, 2, 3 ,..., $n$. Pe fiecare cablu există cel puţin un punct colorat cu fiecare culoare.  Pentru a uşura deplasarea pe cablu, primarul hotărăşte să lege cu sârmă perechi de puncte de aceeaşi culoare, unul de pe primul cablu, iar celălalt de pe al doilea cablu, astfel încât:
-	pentru fiecare culoare să existe o singură pereche de puncte între care să fie legătură;
-	lungimea totală de sârmă folosită să fie minimă.

Între doi stâlpi verticali aflaţi pe malurile unui râu (de o parte şi de alta a râului) se află legate două cabluri bine întinse, paralele cu solul, având distanţa dintre ele egală cu $D$ centimetri. Cablurile sunt folosite pentru traversarea râului în caz de inundaţii. Stâlpii sunt notaţi cu $A$ şi $B$, iar cablurile cu $1$ şi $2$ ca în figura de mai jos. Pe cabluri există desenate câte $N$ puncte colorate cu diverse culori, culorile fiind codificate prin numerele $1, 2, 3,..., K$. Poziţia punctelor pe fiecare cablu este dată prin distanţa faţă de stâlpul $A$ pentru fiecare punct. Punctele de pe fiecare cablu sunt numerotate cu $1, 2, 3 ,..., N$. Pe fiecare cablu există cel puţin un punct colorat cu fiecare culoare.  Pentru a uşura deplasarea pe cablu, primarul hotărăşte să lege cu sârmă perechi de puncte de aceeaşi culoare, unul de pe primul cablu, iar celălalt de pe al doilea cablu, astfel încât:
 
* pentru fiecare culoare să existe o singură pereche de puncte între care să fie legătură;
* lungimea totală de sârmă folosită să fie minimă.

Să se scrie un program care determină lungimea minimă a sârmei ce va fi folosită pentru rezolvarea problemei şi o mulţime de perechi de puncte ce urmează a fi legate pentru a obţine acest minim.
h2. Date de intrare

Fişierul de intrare stalpi.in va conţine:
-	pe prima linie numerele naturale nenule $n$, $d$ separate printr-un spaţiu;
-	pe a doua linie $n$ perechi de numere, formate din distanţa faţă de stâlpul A la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul 1;
-	pe a treia linie $n$ perechi de numere, formate din distanţa faţă de stâlpul A la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul 2.

Fişierul de intrare $stalpi3.in$ va conţine:
 
* pe prima linie numerele naturale nenule $N$, $D$ separate printr-un spaţiu;
* pe a doua linie $N$ perechi de numere, formate din distanţa faţă de stâlpul $A$ la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul $1$;
* pe a treia linie $N$ perechi de numere, formate din distanţa faţă de stâlpul $A$ la fiecare punct şi culoarea asociată punctului, separate prin câte un spaţiu, aflate pe cablul $2$.

h2. Date de ieşire

Fişierul de ieşire stalpi.out va conţine pe prima linie valoarea minimă cerută, iar pe următoarele $k$ linii numerele de ordine ale punctelor ce vor fi legate cu sârmă, separate printr-un spaţiu, întâi cele de pe cablu 1, urmate de cele de pe cablu 2, în ordinea crescătoare a culorilor.

Fişierul de ieşire $stalpi3.out$ va conţine pe prima linie valoarea minimă cerută, iar pe următoarele $K$ linii numerele de ordine ale punctelor ce vor fi legate cu sârmă, separate printr-un spaţiu, întâi cele de pe cablu $1$, urmate de cele de pe cablu $2$, în ordinea crescătoare a culorilor.

h2. Restricţii

* $1 ≤ $n$ ≤ 10000$
* $1 ≤ $k$ ≤ 100$
* $1 ≤ $d$ ≤ 1000$
* Distanţa dintre cei doi stâlpi A şi B este 30000.
* Distanţele de la stâlpul A la puncte sunt numere naturale.
* Distanţa minimă va fi afişată trunchiată la primele 3 zecimale.

* $1 ≤ N ≤ 10000$
* $1 ≤ K ≤ 100$
* $1 ≤ D ≤ 1000$
* Distanţa dintre cei doi stâlpi $A$ şi $B$ este 30000.
* Distanţele de la stâlpul $A$ la puncte sunt numere naturale.
* Distanţa minimă va fi afişată trunchiată la primele $3$ zecimale.

* Toate punctele de pe un cablu sunt distincte.

* Se acordă  40% din punctaj pentru determinarea corectă a minimului din cerinţă.

* Se acordă $40%$ din punctaj pentru determinarea corectă a minimului din cerinţă.

h2. Exemplu
table(example). |_. stalpi3.in |_. stalpi3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|3 100
50 1 200 2 100 1
250 2 100 1 300 2
|211.803
3 2
2 1

|
h3. Explicaţie

...

Sunt $N=3$ perechi de puncte, $K=2$ culori, codificate cu $1$ şi $2$.
Necesarul minim de sârmă este $211.803$.
Se leagă punctul $P3$ de punctul $Q2$ (ambele au culoarea $1$).
Se leagă punctul $P2$ de punctul $Q1$ (ambele au culoarea $2$).
Exemplul corespunde imaginii de mai jos.
 
!problema/stalpi3?stalpi.jpg!

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

5603