T116122 游戏

 展开

题目背景

小 Y 和小 Z 是一对好朋友，他们在玩一个游戏。游戏只有一个回合

Update：

更新题目加粗部分。

题目描述

首先有一个牌堆，一共有 $n$ 张牌，第 $i$ 张牌上有一个数字 $a_i$ 。

小 Z 先取牌，他可以从堆顶开始取连续若干张牌（可以不取），取完的牌拿在手上，也就是不在牌堆里了。

然后小 Y 取牌，同样，她也可以从堆顶开始取连续若干张牌（可以不取）。

如果一个人手上的牌的数字和大于 $X$ 那么他的分数就是 $0$，否则分数就是数字和。

分数高的人获胜。

小 Z 为了获胜，使用了透视挂，即他知道牌堆里牌的顺序。

现在问你对于满足 $1 \leq X \leq K$ 的所有整数 $X$ ，哪些可以使得小 Z 有必胜策略，即小 Z 取完后，不管小 Y 怎么取都会输。

注意：平局不算赢。

输入格式

第一行一个正整数 $n$，表示牌堆里有几张牌。

第二行 $n$ 个用空格隔开的正整数，第 $i$ 个数表示第 $i$ 张牌上的数字 $a_i$，第一张牌是堆顶。

第三行一个正整数 $K$ ，含义见题目描述。

输出格式

第一行一个整数 $ans$，表示满足要求的 $X$ 的个数。

第二行 $ans$ 个正整数，从小到大依次输出满足要求的 $X$，用空格隔开。

特别得，如果 $ans$ 是零，就不用输出第二行。

输入输出样例

输入 #1

5
1 4 3 2 2
5

输出 #1

3
1 2 3

说明/提示

注意：本题采用捆绑测试，只有当你通过一个subtask中的所有测试点后，你才能拿到这个subtask的分数。

对于 $100 \%$ 的数据 ：$1\leq n,K \leq 10^6,1\leq a_i \leq K$。

subtask1（$3 \%$）：$n=1$。

subtask2（$14 \%$）：$K=1$。

subtask3（$20 \%$）：$n,K \leq 100$。

subtask4（$33 \%$）：$n,K \leq 3333$。

subtask5（$30 \%$）：无特殊限制。

样例解释：

$X=1,2,3$ 时，小 Z 取一张牌，小 Y 不管怎么取都是零分。

$X=4$ 时，小 Z 如果取 $1$ 张，那么小 Y 取 $1$ 张小 Y 就赢了；否则小 Z 只能是零分。

$X=5$ 时，小 Z 如果取 $1$ 张，那么小 Y 取 $1$ 张小 Y 就赢了；小 Z 如果取了 $2$ 张，小 Y 也取 $2$ 张，平局；否则小 Z 只能是零分。