Page 125 - MATINF Nr.2

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 125

Exemplu

lant.in lant.out Explicat , ie

5 3 2 1 5
4 2
4 2
1 5
5 3 3

Lat , ul elementar [1, 5, 3] are lungimea ma-
xim˘a, 2.

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 2 MB.
Doru Constantin, Pites , ti
ˆ
I 27 (stalpi). Intre doi stˆalpi verticali aflat , i pe malurile unui rˆau (de o parte s , i de alta a rˆaului)
se afl˘a legate dou˘a cabluri bine ˆıntinse, paralele cu solul, avˆand distant , a dintre ele egal˘a cu d
centimetri. Cablurile sunt folosite pentru traversarea rˆaului ˆın caz de inundat , ii. Stˆalpii sunt
notat , i cu A s , i B, iar cablurile cu 1 s , i 2 ca ˆın figura de mai jos. Pe cabluri exist˘a desenate
cˆate n puncte colorate cu diverse culori, culorile fiind codificate prin numerele 1, 2, 3, . . . , k.
Pozit , ia punctelor pe fiecare cablu este dat˘a prin distant , a fat , ˘a de stˆalpul A, pentru fiecare punct.
Punctele de pe fiecare cablu sunt numerotate cu 1, 2, 3, . . . , n. Pe fiecare cablu exist˘a cel put , in
un punct colorat cu fiecare culoare. Pentru a us , ura deplasarea pe cablu, primarul hot˘ar˘as , te s˘a
lege cu sˆarm˘a perechi de puncte de aceeas , i culoare, unul de pe primul cablu, iar cel˘alalt de pe al
doilea cablu, astfel ˆıncˆat:

1. pentru fiecare culoare s˘a existe o singur˘a pereche de puncte ˆıntre care s˘a fie leg˘atur˘a;
2. lungimea total˘a de sˆarm˘a folosit˘a s˘a fie minim˘a.

Cerint , ˘a
S˘a se scrie un program care determin˘a lungimea minim˘a a sˆarmei ce va fi folosit˘a pentru
rezolvarea problemei s , i o mult , ime de perechi de puncte ce urmeaz˘a a fi legate pentru a obt , ine
acest minim.
Date de intrare

Fis , ierul de intrare stalpi.in va cont , ine:

1. pe prima linie numerele naturale nenule n, d separate printr-un spat , iu;
2. pe a doua linie n perechi de numere, formate din distant , a de la de stˆalpul A la fiecare
punct aflat pe cablul 1 s , i culoarea asociat˘a punctului, separate prin cˆate un spat , iu;
3. pe a treia linie n perechi de numere, formate din distant , a de la stˆalpul A la fiecare punct
aflat pe cablul 2 s , i culoarea asociat˘a punctului, separate prin cˆate un spat , iu.

Date de ies , ire
Fis , ierul de ies , ire stalpi.out va cont , ine pe prima linie valoarea minim˘a cerut˘a, iar pe
urm˘atoarele k linii numerele de ordine ale punctelor ce vor fi legate cu sˆarm˘a, separate printr-un
spat , iu, ˆıntˆai cele de pe cablul 1, urmate de cele de pe cablul 2, ˆın ordinea cresc˘atoare a culorilor.

Restrict , ii s , i preciz˘ari
• 1 ≤ n ≤ 10000
• 1 ≤ k ≤ 100