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