SWERC 2006 - The Right Tip

[mogers]

hi all

The Right Tip at NuevoPortal

i'm quite frustrated with this problem. I solved this problem in swerc 2006 (as contestant) but now i tried to solve it at 'nuevoportal' and i get WA.

This problem is easy, shouldn't be enough a greedy algorithm ?
I can't figure why i'm having WA[/url]

[david]

Because the greedy algorithm is wrong in this case (not all coin values are divisible by the previous one).
Don't be mistaken, this problem is not so easy. What happens is that at SWERC, test data for this problem was very weak and almost everybody got accepted with the (incorrect) greedy algorithm.

[mogers]

it's been a long time since i wrote the post

i don't know if the test data was weak at swerc. in fact, at swerc i didn't use a greedy algorithm. I was confused
sorry,

[Marius]

I can't figure out how to solve this problem. Could you give me some hints, please? Thank you in advance.