#P17716. [HexOI Round 1] 变魔术 / magic
[HexOI Round 1] 变魔术 / magic
背景
题目来源:【HT-130-Div.3】核桃 CSP-J 组模拟赛
HexOI 欢迎您。
题目描述
小 Hex 有 块积木!每块积木都有一个「美丽度」,第 块积木的美丽度为 。
现在小 Hex 想向小 Toast 表演魔术。他希望用一种特殊的魔术技巧来整理他的积木,最后只留下小 Toast 最喜欢的积木。
具体地,他整理积木的方法如下:
- 小 Hex 有一个淘汰盒。初始时,他手上有所有的积木,并且淘汰盒是空的。
- 小 Hex 会把他目前手上所有的积木分为若干堆,并计算每堆所有积木的美丽度之和;
- 小 Hex 会选择美丽度之和最高的一堆积木(如果有并列则任取一堆),保留这一堆积木,并把其他所有的积木放到淘汰盒中;
- 如果操作结束后小 Hex 只剩恰好一个积木,那么他会把这个积木展示给小 Toast;否则,回到「第 2 步」继续。
然而,小 Hex 并不知道小 Toast 最喜欢的积木,因此他要对所有的情况做好准备。现在他想知道,对于所有的 ,假设小 Toast 喜欢第 块积木,他能否恰好选择出小 Toast 喜欢的那个积木?
输入格式
第一行一个正整数 。
第二行 个正整数 。
输出格式
一行 个整数,第 个数表示假设小 Toast 喜欢第 块积木时,小 Hex 能否恰好选出他喜欢的积木。为 表示可以,为 表示不行。
3
1 2 3
0 1 1
6
1 10 5 3 7 9
0 1 1 0 1 1
提示
【样例 1 解释】
小 Hex 可以用下面的方法来选出第二块积木:
- 把所有积木按编号分为 和 两堆积木,此时两堆积木的美丽度之和分别为 。保留第一堆积木,将 号积木放进淘汰盒。
- 把 号积木按编号分为 和 两堆积木,此时两堆积木的美丽度之和分别为 。保留第二堆积木,将 号积木放进淘汰盒。
- 此时,小 Hex 只剩下 号积木。
小 Hex 可以用下面的方法来选出第三块积木:
- 把所有积木按编号分为 , 和 三堆积木,此时三堆积木的美丽度之和分别为 。保留第三堆积木,将 号积木放进淘汰盒。
- 此时,小 Hex 只剩下 号积木。
可以证明,无论小 Hex 怎样操作,他都无法选出第一块积木。
【样例 3】
见选手目录下的 magic/magic3.in 与 magic/magic3.ans。
该样例满足测试点 的约束条件。
【样例 4】
见选手目录下的 magic/magic4.in 与 magic/magic4.ans。
该样例满足测试点 的约束条件。
【样例 5】
见选手目录下的 magic/magic5.in 与 magic/magic5.ans。
该样例满足测试点 的约束条件。
【样例 6】
见选手目录下的 magic/magic6.in 与 magic/magic6.ans。
该样例满足测试点 的约束条件。
【数据范围】
对于所有测试数据,保证:
- 。
- 对于所有 ,均有 。
::cute-table{tuack}
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| ^ | ^ | ||
| ^ | A | ||
| ^ | B | ||
| 无 | |||
特殊性质 A:保证 。
特殊性质 B:对于所有 ,都有 或 。