jaswanthi's blog

Round 313 Div2 Problem A, Rephrased as "Minimum unfortunate Sum Greater than 1"
By jaswanthi, 9 years ago, In English

Codeforces Round 313 Problem A: Currency System in Geraldion

How to solve if we rephrase the problem statement to find " Minimum unfortunate sum that is greater than 1 "?

If the input notes denomination includes "1", obviously there won't be any "unfortunate sum".

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Are you from the future?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can make everything with 2 and 3

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the answer is that with a banknote of value 1 you can make any sum you want,if you don't have value 1 then this is smallest value that cannot me made.

The problem statement was bad, took me 5 minutes to understand the ubove statement, which is very bad.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think I didn't figure it out the ultra-simple idea in the contest. So solving it with a normal dp up to 10^7 would solve it. You just search for the first sum in the dp array which is not formed.

→ Reply