|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초||512 MB||13||5||2||22.222%|
A group of N pirates found K gold coins. They must decide on a way to distribute the coins amongst themselves. They have agreed on the following rules:
The oldest pirate proposes a distribution. (You can assume that all the pirates’ ages are distinct.) A distribution assigns an non-negative integer number of coins to each pirate such that the sum of these numbers equals K.
Then, each pirate will vote either ‘yes’ or ‘no’ on the proposal. The number of ‘yes’ votes required for the proposal to pass depends on the number of pirates. If there are X pirates, then V [X] ‘yes’ votes are required for the proposal to pass. If the proposal passes, the coins are assigned according the proposed distribution and the process ends. Otherwise, the oldest pirate is thrown overboard and the process is repeated without him.
The pirates act according to the following rules. The rules are given in order of priority; for example, rule 2 is only applied to distinguish between multiple options that are optimal according to rule 1.
If there are still multiple choices that fit these rules, he will maximize the gold received by the secondoldest pirate, then the third-oldest pirate, etc. If there are multiple options that are optimal according to these rules, then the pirate chooses an action arbitrarily. (You can assume that the answer to this problem does not depend on the pirate’s choice in this case.) Additionally, all the pirates are perfectly logical and know all the information contained in this problem statement. They cannot form agreements or coalitions because they do not trust each other.
We will number the pirates from 1 to N, where these are numbered from the youngest (pirate 1) to the oldest (pirate N).
If there were only i pirates (where i = 1, . . . , N), how many coins would the oldest of them get?
The first line of input will be the number N (2 ≤ N ≤ 106).
The second line of input will be the integer K (1 ≤ K ≤ 1018).
The next N lines of input contain V [i] (1 ≤ V [i] ≤ i) indicating the number of ‘yes’ votes required for a proposal to pass if there are i pirates remaining (i = 1, . . . , N).
The output should consist of N integers, printed one per line. The ith line of output is the number of coins that the ith pirate would get if they were the oldest pirate; in other words, if only pirates 1, . . . , i existed. If the ith pirate is thrown overboard, output -1 on the ith line.
5 100 1 1 2 2 3
100 100 99 99 98
If there are 2 pirates left, pirate 2 can propose that all of the gold coins go to him. Only 1 vote is required for this proposal to pass, so he can guarantee that it passes by voting for it.
If there are 3 pirates left, pirate 3 needs someone else to vote for his proposal. He can ensure this by giving 1 coin to pirate 1 and 99 to himself. Pirate 1 knows that if the proposal doesn’t pass, he will receive nothing. So a single coin is enough to secure his vote.
If there are 4 pirates left, pirate 4 gives 1 gold coin to pirate 2 and 99 to himself.
If there are 5 pirates left, pirate 5 gives 1 gold coin to pirates 1 and 3 and keeps 98 coins for himself.
5 100 1 2 3 4 4
100 -1 -1 -1 100
In this case, a full consensus is required for a proposal to pass, except when there are 5 pirates, in which case only 4 of the 5 votes are required.
If there is full consensus required, and there are 2 or more pirates, the youngest pirate will vote against the proposal to maximize their coins and also throw the most pirates overboard.
In the case where there are 5 pirates, the oldest pirate will propose to give himself 100 coins. Everyone except the youngest pirate will vote ’yes’, because if this proposal doesn’t pass, the youngest pirate will get all of them thrown overboard and then take the coins for himself when only he remains. Since the pirates don’t want to be thrown overboard, they will vote ’yes’, even though the oldest pirate will offer them nothing.
4 100 1 1 2 3
100 100 99 97
The first three cases were explained in Sample Input 1.
When there are 4 pirates, the oldest pirate needs 3 votes. He will give 2 coins to the youngest pirate and 1 coin to the second-youngest pirate, keeping the rest for himself.
4 2 1 1 2 3
2 2 1 -1
The situation is the same as in Example 3, but now there are only 2 coins. With 1, 2 or 3 pirates, we have the same situations as in Example 3.
With 4 pirates, the oldest pirate does not have enough coins to ensure the 3 votes which he needs, so he will be thrown overboard.