Parliament
Time limit2sMemory limit128 MB
Given seat counts for N parties, find the maximum-seat coalition that has more than half the total seats but loses majority if any single member is removed.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Sorting, Combinatorics
- Solved
- No attempts yet
Problem
A parliament has N parties, and each party holds some number of seats.
Some parties want to form a coalition. A coalition is valid if the total number of seats held by its parties is more than half of all seats.
If a valid coalition remains valid after removing one of its member parties, then the coalition is not clean. A clean coalition is a valid coalition that is not in that situation.
Find a clean coalition whose total number of seats is as large as possible.
Input
The first line contains the number of parties N. (1 <= N <= 300)
The second line contains the number of seats held by each party, in party-number order. Each value is a nonnegative integer not greater than 100000.
Parties are numbered from 1 to N, and the sum of all seat counts is at most 100000.
Output
Find one clean coalition with the maximum possible total number of seats.
On the first line, print the number of parties in the coalition.
On the second line, print the party numbers in increasing order, separated by spaces.