P6015 [CSGRound3] Game

Player Y and Player Z are a pair of good friends, and they are playing a game. **The game has only one round**.

There is a deck with a total of $n$ cards. The $i$-th card has a number $a_i$ written on it, where the first card is the top of the deck. Player Z draws first. He may draw a consecutive number of cards starting from the top of the deck (**he may draw $0$ cards**). The drawn cards are held in his hand, meaning they are removed from the deck. Then Player Y draws. Similarly, she may draw a consecutive number of cards starting from the top of the deck (**she may draw $0$ cards**). If the sum of the numbers on a player's hand is greater than $X$, then their score is $0$; otherwise, their score equals the sum. The player with the higher score wins; **if the scores are equal, then nobody wins**. In order to win, Player Z uses a cheating tool (x-ray vision), meaning he knows the number written on every card in the deck. Now, for all integers $X$ satisfying $1 \leq X \leq K$, determine which values of $X$ allow Player Z to have a winning strategy, i.e., after Player Z finishes drawing, no matter how Player Y draws, Player Y will definitely **lose**.

The first line contains an integer $n$, representing the number of cards in the deck. The second line contains $n$ integers $a_{1\dots n}$, representing the number written on each card. The third line contains a positive integer $K$, as described in the statement.

The first line contains an integer, representing the number of values $X$ that satisfy the requirement. The second line outputs the values of $X$ that satisfy the requirement in increasing order, separated by spaces.

**[Sample Explanation]** When $X=1,2,3$, Player Z draws one card, and no matter how Player Y draws, Player Y will get a score of $0$. When $X=4$, if Player Z draws $1$ card, then if Player Y draws $1$ card, Player Y will win; otherwise, Player Z can only get a score of $0$. When $X=5$, if Player Z draws $1$ card, then if Player Y draws $1$ card, Player Y will win. If Player Z draws $2$ cards, then Player Y also draws $2$ cards, resulting in a tie. Otherwise, Player Z can only get a score of $0$. --- **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (3 points): $n = 1$. - Subtask 2 (14 points): $K = 1$. - Subtask 3 (20 points): $n, K \le 100$. - Subtask 4 (33 points): $n, K \le 3333$. - Subtask 5 (30 points): no special restrictions. For $100\%$ of the testdata, $1 \leq n, K \leq 10^6$, $1 \leq a_i \leq K$. Translated by ChatGPT 5