11366 - Circle of Debt

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

11366 - Circle of Debt

If the judge data is the same as the original contest data, I think it is wrong:

The forth case is:

Code: Select all

``````1 5 0
1 0 0 0 0 0
0 1 1 1 2 10
0 0 5 0 0 5``````
This means that before the exchange Alice has 100, Bob has 100 and Cynthia has 25 crowns. Since Alice has to pay Bob 1 crown, and Bob has to pay Cynthia 5 crowns, after the exchange Alice has 99, Bob has 96 and Cynthia has 30 crowns. Since all amounts are below 100 crowns, no one can have the 100 crown note originally owned by Alice, so the answer should be 'impossible'.
Still the contest data (and the official judge solution) says that it can be done with 13 exchanges.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Re: 11366 - Circle of Debt

little joey wrote:If the judge data is the same as the original contest data, I think it is wrong:

The forth case is:

Code: Select all

``````1 5 0
1 0 0 0 0 0
0 1 1 1 2 10
0 0 5 0 0 5``````
This means that before the exchange Alice has 100, Bob has 100 and Cynthia has 25 crowns. Since Alice has to pay Bob 1 crown, and Bob has to pay Cynthia 5 crowns, after the exchange Alice has 99, Bob has 96 and Cynthia has 30 crowns. Since all amounts are below 100 crowns, no one can have the 100 crown note originally owned by Alice, so the answer should be 'impossible'.
Still the contest data (and the official judge solution) says that it can be done with 13 exchanges.
originally Cynthia has 105 crowns.
this data has no problem.