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

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


Timp maxim de executie/test:
1.7 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Îti continui cariera în constructii de drumuri. Pentru a moderniza drumul de la Iasi la Alba-Iulia trebuie sa construiesti tuneluri pe sub munti sau viaducturi deasupra vailor.
Din lipsa de fonduri poti construi maximum K tuneluri/viaducturi.
Pentru a proiecta drumul desenezi pe o foaie de matematica un sistem de coordonate cartezian. Patratelele de pe foaie au latura egala cu 1 si colturile în puncte de coordonate întregi.
Axa OY este figurata pe marginea din stânga a foii.
Drumul este figurat ca o linie frânta formata dintr-o succesiune de N segmente, oricare doua segmente consecutive având un capat comun. Un segment poate fi:
a. latura orizontala a unui patratel (segment orizontal de lungime 1), ceea ce semnifica faptul ca drumul ramâne la aceeasi cota de nivel în zona de teren respectiva.
b. diagonala unui patratel (un segment de lungime sqrt(2)) care semnifica faptul ca drumul urca sau coboara în zona de teren respectiva.
Primul segment are prima extremitate pe axa OY.
Un tunel este un segment orizontal trasat pe sub un munte (uneste în linie dreapta extremitatea de început si extremitatea de sfârsit a muntelui).
Un viaduct este un segment orizontal trasat deasupra unei vai (uneste în linie dreapta extremitatea de început si extremitatea de sfârsit a vaii).
O masina circulând cu viteza legala va parcurge un patratel în A secunde (pentru cazul a.), respectiv în B secunde (pentru cazul b.) Daca masina s-ar deplasa prin tunel sau pe un viaduct, timpul necesar pentru a strabate un patratel este C secunde.

Cerinta
Scrieti un program care, pentru o configuratie a drumului data, determina timpul minim necesar unei masini pentru a se deplasa de la Iasi la Alba-Iulia, în conditiile în care s-au construit maxim K tuneluri/viaducturi.

Date de intrare
Fisierul de intrare drum.in contine pe prima linie 3 numere naturale separate prin câte un spatiu A B C, cu semnificatia din enunt. Pe cea de a doua linie se afla doua numere naturale separate prin spatiu N K, cu semnificatia din enunt. Pe cea de a treia linie se afla o secventa de N caractere care descriu drumul. Al i-lea caracter din secventa este: R daca al i-lea segment ramane orizontal (drumul ramâne la aceeasi cota de nivel); S daca în al i-lea segment drumul urca; J daca în al i-lea segment drumul coboara.

Date de iesire
Fisierul de iesire drum.out va contine o singura linie pe care va fi scris timpul minim necesar unei masini pentru a parcurge drumul dupa construirea a maxim K tuneluri/viaducturi.

Restrictii
1 <= A, B, C <= 100
1 <= N <= 100 000
1 <= K <= 300

Exemplu
drum.in drum.out Explicatie

10 20 15
16 2
RSRJSSJJRRJJRJSS


235
Drumul este cel figurat cu linie subtire în imaginea precedenta. S-au construit un tunel (de la abscisa 4 la abscisa 8) si un viaduct (de la abscisa 11 la abscisa 16). Dupa modernizare, drumul poate fi codificat astfel:
RSRJTTTTRRJVVVVV (unde T reprezinta tunel, iar V reprezinta viaduct)
Timpul minim de necesar pentru parcurgerea drumului este:
10*4+20*3+9*15=235
Deoarece K=2 nu ai construit un tunel si sub primul munte.

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, 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, pipe, 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
Software recomandat
surse trimise | ajutor