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 ?

# | User | Rating |
---|---|---|

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Um_nik | 3297 |

4 | Syloviaely | 3274 |

5 | LHiC | 3216 |

6 | Petr | 3161 |

7 | Benq | 3130 |

8 | ko_osaga | 3124 |

9 | Swistakk | 3089 |

10 | dotorya | 3060 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Swistakk | 150 |

5 | Vovuh | 150 |

7 | csacademy | 147 |

8 | Errichto | 145 |

8 | Um_nik | 145 |

8 | PikMike | 145 |

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 ?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2018 14:58:43 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

This is a dynamic programming problem. First learn something about it, then approach this problem

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?

where we computing the tasks again and again. how would you tell this is dp?

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.

It can be solved in O(1).

We want to count the number of solutions of

x_{1}+ 5x_{2}+ 10x_{3}+ 25x_{4}+ 50x_{5}=N.x_{1}must be congruent with n%5, so is equivalent to count the number of solutions ofx_{1}+x_{2}+ 2x_{3}+ 5x_{4}+ 10x_{5}= ⌊N/ 5⌋ =MLet's suppose (i.e

x_{i}= 5a_{i}+r_{i}), fori≤ 3.We can brute force all possibilities of

r_{i}, now we have to count the solutions ofa_{1}+a_{2}+ 2a_{3}+x_{4}+ 2x_{5}= ⌊ (M-r_{1}-r_{2}- 2r_{3}) / 5⌋ =PGrouping, (

a_{1}+a_{2}+x_{4}) + 2(a_{3}+x_{5}) =Pwhich can be solved byi 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)