← 返回题目列表

Codeforces · 1178/A

A. 总理

中文机器翻译题面 查看原题

爱丽丝是国家重构党的领袖,她即将成为首相。

选举刚刚举行。有 $$$n$$$ 个派对,编号从 $$$1$$$ 到 $$$n$$$。 $$$i$$$ 党在议会中获得了 $$$a_i$$$ 席位。

Alice 的队伍编号为 $$$1$$$。为了成为总理,她需要建立一个由她的政党和可能还有其他一些政党组成的联盟。她需要满足两个条件:

- 联盟中所有政党的席位总数必须是所有席位的严格多数,即必须严格超过一半席位。例如,如果议会有 $$$200$$$(或 $$$201$$$)个席位,则多数席位为 $$$101$$$ 或更多席位。
- Alice 所在政党的席位必须比联盟中任何其他政党至少多 $$$2$$$ 倍。例如,要邀请具有 $$$50$$$ 席位的派对,Alice 的派对必须至少拥有 $$$100$$$ 席位。

例如,如果 $$$n=4$$$ 和 $$$a=[51, 25, 99, 25]$$$ (请注意,Alice 的一方有 $$$51$$$ 席位),则以下集合 $$$[a_1=51, a_2=25, a_4=25]$$$ 可以创建一个联盟,因为这两个条件都满足。但是,以下集合不会创建联盟:

- $$$[a_2=25, a_3=99, a_4=25]$$$ 因为 Alice 的队伍不在那里;
- $$$[a_1=51, a_2=25]$$$ 因为联盟应该拥有严格多数;
- $$$[a_1=51, a_2=25, a_3=99]$$$ 因为爱丽丝的政党应该比联盟中任何其他政党拥有至少 $$$2$$$ 倍的席位。

Alice 不必最小化联盟中各方的数量。如果她愿意,她可以邀请任意数量的聚会(只要满足条件)。如果爱丽丝的政党有足够的人来创建一个联盟,她就不能邀请任何政党。

请注意,Alice 可以邀请整个队伍,也可以不邀请。不能只邀请另一党的部分代表(席位)。换句话说,如果爱丽丝邀请了一个聚会,她就会邀请该聚会的所有代表。

查找并打印任何合适的联盟。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 参与方数量。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) — $$$i$$$ 一方拥有的席位数。

输出

如果不可能存在满足这两个条件的联盟,则输出带有整数 $$$0$$$ 的单行。

否则,假设联盟中有 $$$k$$$ ($$$1 \leq k \leq n$$$) 个政党(Alice 不必最小化联盟中政党的数量),并且它们的索引为 $$$c_1, c_2, \dots, c_k$$$ ($$$1 \leq c_i \leq n$$$)。输出两行,第一行包含整数 $$$k$$$,第二行包含空格分隔的索引 $$$c_1, c_2, \dots, c_k$$$。

您可以按任何顺序打印各方。 Alice 的队伍(编号 $$$1$$$)必须在该列表中。如果有多个解决方案,您可以打印其中任何一个。

示例

输入 #1

3
100 50 50

输出 #1

2
1 2

输入 #2

3
80 60 60

输出 #2

0

输入 #3

2
6 5

输出 #3

1
1

输入#4

4
51 25 99 25

输出#4

3
1 2 4

注意

在第一个示例中,Alice 选择第二方。请注意,她也可以选择第三方或两者。然而,如果没有他们中的任何一个,她就无法成为总理,因为 $$$100$$$ 并不是 $$$200$$$ 中的绝对多数。

在第二个示例中,无法获得多数席位,因为其他政党都太大而无法成为联盟伙伴。

在第三个示例中,Alice 已经拥有多数。

问题陈述中描述了第四个示例。