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