.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » stalpi2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
stalpi2


Timp maxim de execuţie / test:
0.3s
Memorie totala disponibilă / stivă:
4MB / 4MB

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

stalpi2.instalpi2.outExplicaţ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).

autor: Prof. Doru Popescu Anastasiu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: degrade, hora, noroc, test, tren, grad, palma, cs, h, vagoane, scaune, tir, nrcuv2, piata, vocale, prop, poligon, text2, onu2, creioane, exp, donald, young, albine, turn, linie, tub, suma1, triunghi, cod1, pic, zuzu, pav, prieteni1, banda10, numar2, prime1, ziduri, puncte2, texan, part, ucif, numere7, mare, furnica, pavare, cifre3, domino, exp1, coduri, efort, prodmax, char, dartz, operatii, jucarii, cd1, codif, bileprime, echipa, covor, pavari, parcela, grad1, ec, grad2, testament, nrpomi, elicop, triburi1, showroom, cartite
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor