Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | stalpi3.in, stalpi3.out | Sursă | ONI 2011, clasa a 9-a |
| Autor | Doru Popescu Anastasiu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 8192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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.
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.
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.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| stalpi3.in | stalpi3.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
