問題一覧 > 通常問題

No.1515 Making Many Multiples

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 37
作問者 : だれだれ / テスター : nok0nok0
5 ProblemId : 6366 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-19 02:24:40

問題文

$N+2$ 枚のカードと正の整数 $K$ を用いてゲームを行います。各カードにはそれぞれ $1$ つの正の整数が書かれています。

$N$ 枚のカードは $1$ つの山になって置かれています。残りの $2$ 枚はあなたが初めから持っていて、 $1$ 枚には $X$、もう $1$ 枚には $Y$ が書かれています。

あなたは以下の操作を $N$ 回行います。

$(1)$ 山札の一番上のカードを引く。
$(2)$ 今手に持っているカードに書かれた数の和が $K$ の倍数であるとき、$1$ 点を得る。
$(3)$ 手に持っているカードのどれか $1$ 枚を捨てる。

あなたは超能力者なので、山札の上から $i$ 番目のカードには $A_i$ が書いてあることがわかりました。

最適に行動したとき、得られる得点の最大値を求めてください。

入力

$N\ K\ X\ Y$
$A_1\ A_2\ \dots \ A_N$

  • $1 \leq N \leq 2000$
  • $1 \leq K \leq 2000$
  • $1 \leq X, Y, A_i \leq 10^9$
  • 入力はすべて整数

出力

得られる得点の最大値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 3 1 2
3 4 5
出力
3

$1$ 回目の操作で $1$ のカードを、 $2$ 回目の操作で $2$ のカードを捨てることで、$3$ 点を得ることができます。


はじめ、あなたは $1$ のカードと $2$ のカードを持っています。

$1$ 回目の操作で $3$ のカードを引きます。このとき、 $1+2+3=6$ は $3$ の倍数なので $1$ 点を得ます。

$1$ のカードを捨てます。あなたが持っているのは $2$ と $3$ のカードです。

$2$ 回目の操作で $4$ が書かれたカードを引きます。$2+3+4=9$ は $3$ の倍数なので $1$ 点を得ます。

$2$ のカードを捨てます。あなたが持っているのは $3$ と $4$ のカードです。

$3$ 回目の操作で $5$ が書かれたカードを引きます。 $3+4+5=12$ は $3$ の倍数なので $1$ 点を得ます。

捨てるカードはなんでもよいです。


以上のように行動することで $3$ 点を得られ、これが最大です。

サンプル2
入力
5 100 1 1
1 1 1 1 1
出力
0

どのように行動しても $1$ 点も得られません。

サンプル3
入力
10 3 2 2
3 3 3 3 3 2 2 2 2 2
出力
6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。