IX Olimpiada Informatyczna 2001/2002
|
Task: zam
|
Author: Zbigniew Czech
|
I stage contest |
Megachip IV the Splendid, the king of Byteotia, intends to give his pretty daughter, princess Ada, away in marriage. He asked her what husband she wanted to have. The princess answered that she expected her future spouse to be wise, and also neither parsimonious nor squandering. The king pondered on what trials the candidates should be put to in order to choose the best one for his daughter. After long musings he found that it would serve best to use a castle he had built for entertainment of the inhabitants of Byteotia. The castle contains a large number of chambers where treasures of the kingdom are gathered. The chambers, connected by corridors, may be visited by the subjects to admire the wonderful things exhibited there. To visit a chamber one has to pay a certain amount of bytealers (a bytealer is a monetary unit of Byteotia). A visit in the castle begins in the entrance chamber.
The king handed a purse to every candidate for a princess' husband. There was the same amount of bytealers in each purse. He asked each candidate to choose his way of visiting some number of the castle's chambers starting from the entrance one and ending in the one the princess stays in. Each candidate was required to spend on his tour exactly the sum that was in his purse. Squanderers that spent too much money on their way did not reach the princess' chamber. On the other hand the parsimonious candidates appeared there with nonempty purses, and the princess sent them away to empty their purses.
Unfortunately, till now no candidate has managed to cope with the king's task, and the princess is still looking forward to her perfect match. Why don't you want to be put to the test? You may write a program that would help the poor princess.
5 6 3 4 9 1 2 3 4 5 2 4 5 4 1 5 1 2 2 3 3 1a correct answer is in the following output file zam.out:
3 2 4