2016 Canadian Computing Olympiad
Day 2, Problem 3 - Pirates
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 a 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 − 1] '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.
- A pirate will act to prevent himself from being thrown overboard.
- A pirate will act to maximize the number of coins he receives.
- A pirate will act to maximize the number of pirates thrown overboard (excepting himself, because rule 1 takes priority).
- A pirate will act to maximize the number of coins received by the oldest pirate. If there are still multiple choices that fit these rules, he will maximize the gold received by the second-oldest 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 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).
For 5 of the 25 available marks for this problem N ≤ 2000.
For an additional 5 of the 25 available marks for this problem max(1, i − 3) ≤ V[i] ≤ i for all i = 1, …, N.
For an additional 5 of the 25 available marks for this problem K = 1018.
The output should consist of N integers, printed one per line. The i-th line of output is the number of coins that the i-th pirate would get if they were the oldest pirate. In other words, if only pirates 1, …, i − 1 existed. If the i-th pirate is thrown overboard, output
-1 on the i-th line.
Sample Input 1
5 100 1 1 2 2 3
Sample Output 1
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.
Sample Input 2
5 100 1 2 3 4 4
Sample Output 2
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.
Sample Input 3
4 100 1 1 2 3
Sample Output 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.
Sample Input 4
4 2 1 1 2 3
Sample Output 4
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.
Point Value: 25 (partial)
Time Limit: 15.00s
Memory Limit: 512M
Added: May 14, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
The first 3 pirates would get 100 coins to themselves, but then if the 4th pirate offered the first 2 zero coins each, would they accept because rule 4?
Each pirate will vote No due to Rule 3, except for Pirate 3 in the case where Pirate 4 does not offer him all the coins, in which case he votes No due to Rule 2.
Pirates 1 and 2 vote No because whether Pirate 4 or Pirate 3 is the oldest, they will still get 0 coins. (Pirate 3 simply takes them all for himself.) Thus, to maximise the number of pirates thrown overboard, they vote No. This is because Rule 3 takes precedence over Rule 4.
However, note that this won't happen. Since Pirates 1 and 2 receive 0 coins if Pirate 3 is the oldest, then to win one of their votes, Pirate 4 simply has to offer one of them one coin. Thus Pirate 4 receives 99 coins.