[BalticOI 2008] 选举

题目描述

The citizens of Byteland have recently been voting in the parliamentary elections. Now, when the results have been published, the parties have to decide on a coalition to form the government. Each party received a certain number of seats in the parliament. The coalition must be a subset of the parties such that together they have strictly more than half of all the seats in the parliament. It is desirable for the coalition to have as many seats as possible, to ensure they can still pass their proposed laws even if a few of their members are absent from a parliament session. A coalition is called redundant if one of its parties can be removed with the remaining ones still having more than half of the seats in the parliament. Of course, such a removable party would effectively have no power — the other members of the coalition would be able to force the laws regardless of its opinion. Write a program that: - reads the election results from the standard input, - finds a non-redundant coalition that has the maximal possible number of seats in the parliament, - writes the description of this coalition to the standard output. ### Input The first line of the standard input contains one integer $n\ (1\le n\le 300)$ — the number of parties that participated in the elections. The parties are numbered from $1$ to $n$. The second line contains n nonnegative integers $a_1,\dots,a_n$, separated by single spaces, where $a_i$ is the number of seats received by the $i$-th party. You may assume that the total number of seats in the parliament will be positive and lower or equal to $100000$. Additionally, in test cases worth $40\%$ of points, the number of parties will not exceed $20$. ### Output The first line of the standard output should contain one integer $k$ — the number of parties in a non-redundant coalition which has the maximal number of seats. The second line should contain $k$ distinct integers separated by single spaces — the numbers of parties that form the coalition. If there are several non-redundant coalitions with the maximal number of seats, you may output any of them. The member parties can be listed in any order. ### 题目翻译 Byteland 国的居民最近一直为议会选举投票。现在,当结果公布的时候,党派不得不决定联合组建政府。 每个党派都会获得议会中的一定席位。联合政府由这些党派中的一部分组成,他们在议会中的席位数之和**严格大于**总席位数的一半。对于联合政府来说,席位越多越好。 一个**过剩**的联合政府是指联合政府中的一个党派被移出后,剩余的联合政府在国会中仍有过半数的席位。 请写一个程序能够: - 读取选举结果; - 找到一个在议会中有着**最大可能席位数**且**不过剩**的联合政府; - 输出这个联合政府的描述。

输入输出格式

输入格式


标准输出的第一行包含一个整数 $n$,表示参加选举的党派数。党派被从 $1$ 到 $n$ 编号。 第二行包含 $n$ 个非负整数 $a_1,\dots ,a_n$,被一个空格隔开,$a_i$ 是第 $i$ 个党派获得的席位数。你可以假设国会中的中的总席位数为小于等于 $10^5$ 的正整数。

输出格式


标准输出第一行应该包含一个整数 $k$,表示无过剩且在议会中有着最大可能席位数的联合政府中含有的党派数。 第二行应该包含 $k$ 个被单个空格隔开的不同整数,表示组成联合政府的党派编号。 如果有不止一个联合政府可以满足要求,你可以输出任意一个。党派的编号可以以任意顺序输出。

输入输出样例

输入样例 #1

4
1 3 2 4

输出样例 #1

2
2 4

说明

对于 $40\%$ 的数据,$n\le 20$; 对于全部数据,$1\le n\le 300$。