A repülőtéren egy X hosszú kijárati folyosó elején állunk, a 0 pontban. A folyosó hosszú, ezért bizonyos szakaszain mozgójárdák segítik az utasokat. A mozgójárdák wi sebessége különböző lehet. Ha gyalogolunk vagy futunk a mozgójárdán, akkor sebességünk (wi+saját sebesség) lesz. A mozgójárdák nem lógnak egymásra, de az lehet, hogy az geyik vége egybeesik a következő elejével. Tegyük fel, hogy gyalogló sebességünk S, de mivel félünk, hogy lekéssük a gépet, R sebességgel futni is tudunk. Sajnos kondink már nem a régi, ezért összesen legfeljebb t másodpercet tudunk futni. (Nem kell mindet kihasználni, és t szétosztható sok kisebb intervallumra is.) Célunk, hogy a lehető leggyorsabban elérjük a folyosó végét.
FeladatÍrjunk programot, ami megadja, hogy optimális esetben hány másodperc kell a folyosó végének eléréséhez.
BemenetA bemenet első sora a tesztesetek T számát adja meg. Minden teszteset első sora öt számot tartalmaz: a folyosó X hosszát (méterben), a gyaloglás S és a futás R sebességét m/s-ban, t értékét (ahány másodpercet futhatunk összesen), és a mozgójárdák N számát. Ezután N sorban egy-egy számhármas következik: a mozgójárdák eleje Bi, vége Ei és sebessége wi. Bi és Ei a kezdőponttól van mérve, méterben. wi mértékegysége m/s.
KimenetMinden tesztesethez legalább hat tizedes pontossággal ki kell írni az optimális stratégia esetén szükséges másodpercek számát. Méretek1 ≤ T ≤ 40. Kis bemenet1 ≤ t ≤ 100. Nagy bemenet1 ≤ t ≤ 106. Példa
TesztadatokCímkékA feladat forrása: Google Code Jam 2011 Round 2/A https://code.google.com/codejam/contest/1150486/dashboard#s=p0&a=0
Algoritmusok: egyszerű implementáció, matematika, fizika
|
Programozás > Feladatok >