|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||10||5||5||71.429%|
The Dutch political system is in turmoil. There have been six coalition governments in the past fourteen years, all of which have fallen before completing their term in office. Recently there have been elections (again), the outcome of which has been described as “impossible” by several political commentators. The only bright spot in this bleak situation is that they have appointed you as the “informateur”. As the informateur it is your task to find a suitable coalition.
Being the rational person you are, you have decided the first negotiation attempt should be started between the parties forming the most stable coalition. A coalition is formed by a set of parties having won a strict majority of seats in the election (i.e. at least 76 seats out of a total of 150). The most stable coalition is one that has the highest chance of completing its term in office. A coalition falls (and new elections must be held) if a single party leaves the coalition. The probability of a coalition completing their term is estimated by the product of the probabilities of each party in the coalition completing their term. This probability is in turn based on historical data.
Find the best coalition and save the Netherlands from becoming a banana republic!
On the first line one positive number: the number of test cases, at most 100. After that per test case:
Note that there are exactly 150 seats divided among all parties (Σsi = 150).
Per test case:
This number should be accurate up to 10-6 relative or absolute precision.
1 4 35 80 25 70 60 60 30 90