Informatika gyűjtemény

Egy szinttel feljebb Repülőtéri futószalagok

2004050607080910

NézetNyomtat

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