Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Stalpi

Adăugată de :
sorynsoo
Sursă :
ONI2011
Autor :
-
Grupă :
Mică
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
300 ms
Limită memorie :
4096 kbytes

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

Cerinţă

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 va conţine pe prima linie numerele naturale nenule n, d separate printr-un spaţiu. Pe a doua linie se află 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 se află 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 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 cablul 1, urmate de cele de pe cablul 2, în ordinea crescătoare a culorilor.

 

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.
• Toate punctele de pe un cablu sunt distincte.
• Se acordă 40% din punctaj pentru determinarea corectă a minimului din cerinţă.

 

Exemple

Date de intrare Date de iesire   Explicaţii
3 100 50 1 200 2 100 1 250 2 100 1 300 2 211.803 3 2 2 1   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).
 

Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !