GCJ2012 Qualification Round Problem B. 問題紹介

Google Code Jam 2012 Qualification Round
Problem B. Dancing With the Googlers 問題紹介

Googler（Google社員）のダンスを見ていて、3人の審判がスコアを付ける…というストーリー。
問題には Googler とかダンスとか関係ありませんw

スコアは 0点〜10点 で、3人の審判が付けるスコアは通常1点差以内に収まります。
(3, 3, 3) や (7, 8, 7) のような形です。
ときどき意外な結果(surprising)になることがあって、2点差のスコアが付けられる場合があります。
(6, 7, 8) や (4, 4, 6) のような形です。
3点差以上のスコアが付けられることはありません。

ダンスした Googler 1人1人について

合計スコア … 3人の審判が付けたスコアの合計

最高スコア … 3人の審判が付けたスコアのうちの最高点

を考えます。

問題では

• 各Googlerの合計スコア
• 意外な結果(surprising)の出た回数
• 目標最高スコア

が与えられるので、目標最高スコアを達成したGooglerが最大何人いるかを求めます。

例:

• 6人の Googler がダンスをして、各々の合計スコアは 29, 20, 8, 18, 18, 21
• 意外な結果(surprising)は 2回
• 目標最高スコア 8点

この場合、6人のスコアの内訳は例えば次のようになっていたと考えられます。

• 29 = (9, 10, 10)
• 20 = (6, 6, 8) ← 意外な結果(surprising)
• 8 = (2, 3, 3)
• 18 = (6, 6, 6)
• 18 = (6, 6, 6)
• 21 = (6, 7, 8) ← 意外な結果(surprising)

最高スコアで 8点以上を取っている Googler は3人なので、この答えは 3 です。

入力データ:

最初の行は問題数 T。以降1行1問のデータが T行続きます。

各行はスペース区切りで複数の整数値を持っています。

最初の値はダンスしたGooglerの人数 N。

次の値は意外な結果(surprising)の出た回数 S。

3つめの値は目標最高スコア p。

その後N個の値がN人のGooglerの合計スコア ti です。

データ制限:

• 1 ≤ T ≤ 100 （問題数は100問、と考えればよいでしょう）
• Small input の場合：1 ≤ N ≤ 3 （ダンスしたGooglerは最大3人）
  Large input の場合：1 ≤ N ≤ 100 （ダンスしたGooglerは最大100人）
• 0 ≤ S ≤ N （意外な結果(surprising)は0回〜最大で全部）
• 0 ≤ p ≤ 10 （目標最高スコアは0点〜10点）
• 0 ≤ ti ≤ 30 （各合計スコアは0点〜30点）
• 少なくともS個の合計スコアは 2点〜28点 の間

解き方はこちら。