H - 3人の昼食 (The Lunch)
Editorial
/
Time Limit: 7 sec / Memory Limit: 600 MB
問題文
ある家には、square1001,E869120,うさぎの3人がいるが、その3人は昼食の値段の 差がああだこうだ、といってけんかが起きてしまう。
そこで、square1001は次のように言った。
「square1001とE869120の合計値段の差、square1001とうさぎの合計値段の差が 両方D以下になるようにしたいです。」
→2人は賛成した。
N個の食品があり、それらの値段はA_iである。また、E個までなら食品を残してもよい。
条件を満たす食品の分け方は何通りあるか。
入力
入力は以下の形式で標準入力から与えられる。
N D E A_1 A_2 : A_N
- 1 行目には、整数 N, D, Eが空白区切りで与えられる。
- 次のN 行には、整数 A_i が与えられる。
出力
食品の分け方の通り数を1行に出力せよ。
制約
- 2≦N≦20
- 0≦D≦1,000,000,000
- 0≦E≦2
- 1≦A_i≦1,000,000,000
部分点
この問題には、部分点が設定されている。
・2≦N≦10を満たすケースすべてに正解した場合は、20点が与えられる。
・11≦N≦20かつ条件を満たす食品の分け方が1000通り以下であるデータセットに正解した場合は、50点が与えられる。
・残りのデータセットすべてに正解した場合は、30点が与えられる。入力例1
3 2 1 2 4 6
出力例1
4
square1001をA, E869120をB, うさぎをCとすると, 以下のように分けることができます。
食品1 | 食品2 | 食品3 | |
方法1 | A | B | × |
方法2 | A | C | × |
方法3 | B | A | C |
方法4 | C | A | B |
入力例2
4 1 1 1 2 3 4
出力例2
10
問題文担当者:E869120