読者です 読者をやめる 読者になる 読者になる

Qualification Round 1 問題C 日本語訳

GoogleCodeJam

問題C
http://code.google.com/codejam/contest/dashboard?c=433101#s=p2

ジェットコースターは楽しい!
人は皆ジェットコースター目当てにテーマパークに行っている、
そう言っても過言ではないだろう。
ジェットコースターに乗る人は1人のときもあるし、
何人かのグループで乗ることもある。
ただ、グループのメンバーがバラバラに乗るのはまっぴらゴメンだよね!
そして皆、一度乗ったらまた並び直して何度でも乗りたがるのさ。
1回乗るためには1人あたり1ユーロの料金だってんだから、安いよね。
さて、君にはジェットコースターの1日あたりの売上を計算してもらうとしようか。

ジェットコースターはk人を一度に乗せることができる。
人々は順番に並んで、1グループの人は必ず皆そろって乗る。
つまり、同じグループの人間なのに別々に乗るなんてことはない。
ジェットコースターは満席かどうかに関わらず発車し、
乗っていた人達はまた同じ順番で列に並び直す。
ジェットコースターは1日にR回走る。

例えば、R=4、k=6 の状況を考えてみる。
また、4つのグループがあり、それらは [1人、4人、2人、1人] とする。
最初にジェットコースターが発車する際は、
先頭の2つのグループ [1人、4人] の合計5人が乗り、1つ空席ができる。
そしてその5人はまた後ろに並び直すので、列の並びは
[2人、1人、1人、4人] となる。
2回目の運転では、[2人、1人、1人] の合計4人が乗車する。
その後、順番待ちの列は [4人、2人、1人、1人] となる。
3回目の運転では [4人、2人] の合計6人が乗車し、
順番待ちの列は [1人、1人、4人、2人] になる。
4回目、すなわち最後の運転では、[1人、1人、4人] の合計6人が乗車する。
こうして、ジェットコースターの売上は 5 + 4 + 6 + 6 = 21ユーロ となる。


■ 入力

最初の行にはテストケースの数Tが記されている。
その後T個のテストケースについて、それぞれ2行ずつ記されている。
最初の行は R, k, N がスペースで区切られて記されている。
次の行ではN個の整数giがスペースで区切られて記されており、
これは g0 が1つ目のグループの人数を表し、
g1 が2つ目のグループを表し、…という具合になっている。

■ 出力

全てのテストケースに対して、"Case #x: y" を記す。
ただし、x は1から始まるテストケースのIDで、
y はジェットコースターの1日の売上(単位はユーロ)である。

■ 制限

1 ≦ T ≦ 50
gi ≦ k

■ Small dataset

1 ≦ R ≦ 1,000
1 ≦ k ≦ 100
1 ≦ N ≦ 10
1 ≦ gi ≦ 10

■ Large dataset

1 ≦ R ≦ 100,000,000
1 ≦ k ≦ 1,000,000,000
1 ≦ N ≦ 1,000
1 ≦ gi ≦ 10,000,000

入力例:

3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

出力例:

Case #1: 21
Case #2: 100
Case #3: 20