問題一覧 > 通常問題

No.2799 Cut and Eat

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : noya2 / テスター : shobonvip 👑 potato167
お気に入りにしたユーザー ProblemId : 11021 / 自分の提出
問題文最終更新日: 2024-06-28 21:03:28
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 435 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,K$.

There are $N$ cakes on a table, and the size of the $i$-th cake is $A_i$.

Alice and Bob will now play a game of cutting and eating these cakes.

Starting with Alice, they alternately perform the following sequence of operations.

  • If there are no cakes on the table, end the game.
  • Otherwise, choose $1$ cake on the table and remove it from the table. Let $S$ be the size of this cake.
  • If $S\le K$, eat this cake.
  • If $S\gt K$, choose $1$ integer $x\ (1\le x\le S-1)$. Place $2$ new cakes of sizes $x,S-x$ on the table.

When each player acts so as to maximize the total size of the cakes they themselves eat throughout the game, find the total size of the cakes Alice eats throughout the game.

Constraints

  • All input values are integers.
  • $1\le N\le 100$
  • $1\le K\le 10^9$
  • $1\le A_i\le 10^9\ (1\le i\le N)$

Input

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

Output

Output the answer.

Sample

Sample 1
Input
1 3
5
Output
2

Here is one example of how the game may proceed.

  • At this point, there is a cake of size $5$ on the table.
  • Alice chooses the cake of size $5$, removes it from the table, and places new cakes of sizes $2,3$ on the table.
  • At this point, there are cakes of sizes $2,3$ on the table.
  • Bob chooses the cake of size $3$, removes it from the table, and eats it.
  • At this point, there is a cake of size $2$ on the table.
  • Alice chooses the cake of size $2$, removes it from the table, and eats it.
  • Since there are no cakes on the table, the game ends.

The total size of the cakes Alice eats throughout the game is $2$.

Sample 2
Input
4 10
1 2 3 4
Output
6

Sample 3
Input
6 28
62 8 628 6 28 628
Output
693

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