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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 1MB

Gigel trebuie să proiecteze instalaţia de apă din propria curte. Curtea are dimensiuni infinite şi nu este împrejmuită. El cunoaşte coordonatele punctului în care se află sursa de apă şi coordonatele punctului unde va instala un robinet. Conducta trebuie proiectată astfel încât cele două puncte să fie unite. Pentru aceasta dispune de n ţevi sub forma unor segmente ale căror lungimi se cunosc, dar care nu pot fi tăiate. Două ţevi se vor conecta astfel încât unghiul dintre ele să fie de 90, 180 , 270 sau 360 grade, adică orice cuplare pe orizontală sau verticală(sus, jos, stânga, dreapta). Unele ţevi sunt roşii iar altele sunt vopsite în albastru. Cele roşii se pot conecta doar pe verticală iar cele albastre doar pe orizontală. Pot exista ţevi de aceeaşi culoare şi lungimi egale, dar fiecare ţeavă se va folosi în instalaţie o singură dată.

Cerinţă

Scrieţi un program care să determine lungimea minimă de ţeavă necesară pentru a uni cele două puncte.

Date de intrare

Fişierul pipe.in are următorul format :
- pe prima linie numărul n;
- pe următoarea linie coordonatele carteziene ale sursei de apă xi yi, numere naturale separate printr-un spaţiu;
- pe următoarea linie coordonatele carteziene ale punctului unde va fi plasat robinetul xf yf,numere naturale separate printr-un spaţiu;
- pe următoarele n linii descrierea fiecărei ţevi realizată astfel: caracterul A pentru culoarea albastru sau R pentru culoarea roşu, urmat de spaţiu şi apoi de un număr natural reprezentând lungimea ţevii.

Date de ieşire

Fişierul pipe.out va conţine pe prima linie un număr reprezentând lungimea minimă determinată sau cuvântul imposibil dacă nu se poate realiza conectarea cu ţevile disponibile.

Restricţii

1 <= n <= 100
1 <=
lungimea fiecărei ţevi <= 290
0 <= xi, yi, xf, yf <= 32000

Exemple

pipe.inpipe.outExplicaţii
8 2 3 6 8 A 9 R 3 R 13 R 8 A 2 R 4 A 15 R 12 37


autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Lot IS 2008: arbnr, center, pitici, sirag1, cod1, tabara, desen1, munte, euclid, sport, stive, bombe, shgraf, paintball, arb, pav
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor