Water Tank — 2004年 愛媛大会 国内予選 問題E

【問題】
 伝次郎氏は理科の先生である.彼は,水の流れに関する革新的な実験をするために水槽を注文していたのだが,今日ちょうどその水槽が届いたところである.

 水槽は,幅100cm,高さ50cm,奥行き30cmの大きさである.水槽の内部を区切るために,数枚の「区切り板」を水槽の側面と平行に水槽の底に設置する.区切り板の横幅はどれも水槽の奥行きである 30cm と等しい.板の高さは水槽の側板の高さである 50cm よりは低い.また,板の高さは,板ごとにどれも異なっている. 区切り板は十分に薄いので,その厚さは無視できるものとする.

 水槽の上方にはいくつかの蛇口があり,実験開始と同時に蛇口を開いて水を水槽へと注ぎ入れる.実験開始時に水槽は空である.あなたの仕事は,水槽内における水の流れをシミュレートするプログラムを書くことである.

【入力】
 入力は,複数のデータセットからなる. D はデータセットの数を表す.
   D
   DataSet1
   DataSet2
   …
   DataSetD

 各データセット (DataSetd , ただし 1 <= d <= D) の形式は次の通りである.
   N
   B1 H1
   B2 H2
   …
   BN HN
   M
   F1 A1
   F2 A2
   …
   FM AM
   L
   P1 T1
   P2 T2
   …
   PL TL

 データセットの各行には1個または2個の整数が現れる.

 N は彼が設置する区切り板の数を表す. Bi はi 番目の区切り板の x座標 (単位はcm) であり,Hi はその区切り板の高さ (単位はcm) を表す.ここで 1 <= i <= N である.
 Hi はどれも異なっている.以下の条件が成り立つと仮定してよい.
   0 < N < 10 ,
   0 < B1 < B2 < ... < BN < 100 ,
   0 < H1 < 50 , 0 < H2 < 50 , ..., 0 < HN < 50.

 M は水槽の上方に設置された水道の蛇口の数を表す. Fj はj番目の蛇口の x座標 (cm単位) であり, Aj はその蛇口から注ぎ込まれる水の流量 (cm3/秒)を表す.ただし 1 <= j <= Mである.
 区切り板の真上に蛇口が来ることはない.すなわち Fj が Bi と一致することはない.
 以下の条件が成り立つと仮定してよい.
   0 < M <10 ,
   0 < F1 < F2 < ... < FM < 100 ,
   0 < A1 < 100, 0 < A2 < 100, ... 0 < AM < 100.

 L は水の高さを測定する回数である. Pk は測定する場所の x 座標 (cm単位) であり, Tk は測定をする時刻 (実験開始からの経過時間,秒単位) である.ただし 1 <= k <= L である.
 Pk が Bi と一致することはない.
 以下の条件が成り立つと仮定してよい.
   0 < L < 10 ,
   0 < P1 < 100, 0 < P2 < 100, ..., 0 < PL < 100 ,
   0 < T1 < 1000000, 0 < T2 < 1000000, ... , 0 < TL < 1000000.

【出力】
 各データセットに対して,実数を1個ずつ含む行を L行出力しなさい.その実数は,指定された時刻 Tk における,指定された x 座標 Pk の水の高さ(cm)を表していること.
 解答の誤差は0.001を超えてはいけない.この条件を満たす限り,小数点以下は何桁数字を表示してもかまわない.
 水槽が満杯になって以後は,水槽の縁から水が溢れ出るのでどのPkの水の高さも水槽の高さと同じ,すなわち 50cm となる.

入力例
2
5
15 40
35 20
50 45
70 30
80 10
3
20 3
60 2
65 2
6
40 4100
25 7500
10 18000
90 7000
25 15000
25 22000
5
15 40
35 20
50 45
70 30
80 10
2
60 4
75 1
3
60 6000
75 6000
85 6000

【出力例】
0.666667
21.4286
36.6667
11.1111
40.0
50.0
30.0
13.3333
13.3333

Comments are closed.

Post Navigation