Repülőtéri futószalagok
Egy repülőtéren állunk, a 0 pontban. Egy X hosszúságú folyosó vezet a kijáratig, ahonnan a gépünk indul. A folyosón néhol futószalagok vannak, mindegyiknek különböző wi sebessége lehet. Amikor egy futószalagon haladsz, a futószalag sebessége hozzáadódik a tiédhez. A futószalagok nem váltanak irányt (mindig előre visznek) és nem fedhetik át egymást, de összeérhetnek.
Sebességed alapból s, de mivel félsz, hogy lekésed a gépet, futhatsz is (R sebességgel), de összesen csak t másodpercig, mert nem igazán jó az állóképességed. Nem kell egyhuzamban végigfutni a t másodpercet, tetszőleges számú részre bonthatod, és különböző szakaszokon futhatsz.
Feladat
Határozzuk meg hat tizedes pontossággal, hogy mennyi idő alatt érhetsz a kijárathoz, ha optimálisan osztod be a futással megtett útszakaszokat!
Bemenet
Az első sor a tesztesetek T száma, ezután T teszteset leírása következik.
Minden teszteset első sora 5 egészt tartalmaz:
- X a folyosó hossza méterben
- S a sétáló sebesség (m/s)
- R a futás sebessége (m/s)
- t a futásra szánható idő másodpercben
- N a futószalagok száma
Ezután N sorban 3-3 egész következik:
- Bi: az i. futószalag kezdőpontja (méterben)
- Ei: az i. futószalag végpontja (méterben)
- wi az i. futószalag sebessége (m/s)
Korlátok
1 ≤ T ≤ 40
1 ≤ S < R ≤ 100
1 ≤ wi ≤ 100
0 ≤ Bi < Ei ≤ X
Ei ≤ Bi+1
Kis bemenetre:
1 ≤ t ≤ 100
1 ≤ X ≤ 100
1 ≤ N ≤ 20
Nagy bemenetre:
1 ≤ t ≤ 1000000
1 ≤ X ≤ 1000000
1 ≤ N ≤ 1000
Kimenet
Minden sor "Case #x: y" alakú, ahol x a teszteset sorszáma, y pedig az optimális idő, 6 tizedes pontossággal.
Példa
Input
|
Output
|
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
