ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1515. Cashmaster

Help pls
Posted by Madhav 15 Jul 2008 08:51
Can any one tell me how to solve this problem using greedy approach pls..?
Re: Help pls
Posted by Denis Koshman 18 Jul 2008 16:08
Initially values till max=0 are reachable. If next coin is higher than max+1, then the answer is max+1. Otherwise max is boosted by its value (that is, values 0...max+ai are reachable). Proceed until you find a hole or you run out of coins.