Programozás‎ > ‎Feladatok‎ > ‎

Repülőtéri mozgójárdák

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.

Bemenet

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

Kimenet

Minden 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éretek

1 ≤ T ≤ 40.
1 ≤ S < R ≤ 100.
1 ≤ wi ≤ 100.
0 ≤ Bi < Ei ≤ X.
Ei ≤ Bi+1.

Kis bemenet

1 ≤ t ≤ 100.
1 ≤ X ≤ 100.
1 ≤ N ≤ 20.

Nagy bemenet

1 ≤ t ≤ 106.
1 ≤ X ≤ 106.
1 ≤ N ≤ 1000.

Példa

Bemenet  Kimenet
3
10 1 4 1 2
4 6 1
6 9 2
12 1 2 4 1
6 12 1
20 1 3 20 5
0 4 5
4 8 4
8 12 3
12 16 2
16 20 1
Case #1: 4.000000
Case #2: 5.500000
Case #3: 3.538095238


Tesztadatok

Címkék

A 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