問題一覧 > 通常問題

No.1515 Making Many Multiples

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 52
作問者 : だれ / テスター : nok0
お気に入りにしたユーザー ProblemId : 6366 / 自分の提出
問題文最終更新日: 2021-05-19 02:24:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 296 (順位表) の他の問題:

Problem Statement

You play a game using $N+2$ cards and a positive integer $K$. Each card has $1$ positive integer written on it.

$N$ of the cards are placed in $1$ pile. You hold the remaining $2$ cards from the beginning: $1$ of them has $X$ written on it, and the other $1$ has $Y$ written on it.

You perform the following operation $N$ times.

$(1)$ Draw the top card of the pile.
$(2)$ If the sum of the numbers written on the cards currently in your hand is a multiple of $K$, gain $1$ point.
$(3)$ Discard any $1$ of the cards in your hand.

Since you are a psychic, you know that the $i$-th card from the top of the pile has $A_i$ written on it.

Find the maximum score you can obtain when you act optimally.

Input

$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$
  • All inputs are integers.

Output

Output the maximum score you can obtain. Print a newline at the end.

Sample

Sample 1
Input
3 3 1 2
3 4 5
Output
3

In operation $1$, discard the card with $1$, and in operation $2$, discard the card with $2$; this way, you can obtain $3$ points.


Initially, you hold the card with $1$ and the card with $2$.

In operation $1$, you draw the card with $3$. Here, $1+2+3=6$ is a multiple of $3$, so you gain $1$ point.

You discard the card with $1$. You now hold the cards with $2$ and $3$.

In operation $2$, you draw the card with $4$ written on it. $2+3+4=9$ is a multiple of $3$, so you gain $1$ point.

You discard the card with $2$. You now hold the cards with $3$ and $4$.

In operation $3$, you draw the card with $5$ written on it. $3+4+5=12$ is a multiple of $3$, so you gain $1$ point.

You may discard any card.


By acting as above, you obtain $3$ points, and this is the maximum.

Sample 2
Input
5 100 1 1
1 1 1 1 1
Output
0

No matter how you act, you cannot obtain even $1$ point.

Sample 3
Input
10 3 2 2
3 3 3 3 3 2 2 2 2 2
Output
6

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