Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Ravaan777's blog

By Ravaan777, history, 12 months ago, ,

hi how to solve the problem change from the spoj (http://www.spoj.com/problems/TPC07/)

i read concrete mathematics chapter 7 about coin change. but i can't able to understand can anybody help me to get idea about solving this problem ?

•
• +7
•

 » 12 months ago, # |   -21 This is a dynamic programming problem. First learn something about it, then approach this problem
•  » » 12 months ago, # ^ |   0 The upper limit of n is quite large, where 1 ≤ n ≤ 1000000000. How to cater for this with DP?Probably there is a more general formula?
•  » » 12 months ago, # ^ |   0 where we computing the tasks again and again. how would you tell this is dp?
•  » » 12 months ago, # ^ | ← Rev. 2 →   -8 Well the idea is for dp, but you need to use matrices to run it fast, in time (50 is the maximal value of a coin).I can explain more if you want.
 » 12 months ago, # | ← Rev. 3 →   0 It can be solved in O(1).We want to count the number of solutions of x1 + 5x2 + 10x3 + 25x4 + 50x5 = N. x1 must be congruent with n%5, so is equivalent to count the number of solutions of x1 + x2 + 2x3 + 5x4 + 10x5 = ⌊ N / 5⌋ = MLet's suppose (i.e xi = 5ai + ri), for i ≤ 3. We can brute force all possibilities of ri, now we have to count the solutions of a1 + a2 + 2a3 + x4 + 2x5 = ⌊ (M - r1 - r2 - 2r3) / 5⌋ = P Grouping, (a1 + a2 + x4) + 2(a3 + x5) = P which can be solved by
 » 12 months ago, # |   0 i finally done it but for large inputs stack overflow but already i using long long data type. so now what to do?(https://ideone.com/i929bQ)