No.2799 Cut and Eat
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2