Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
最少硬币问题
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 60, Accepted users: 42
Problem 10270 : No special judgement
Problem description
  设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬 币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。 对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。

Input
  输入的第一行中只有1 个整数给出n的值,第2 行起每 行2 个数,分别是T[j]和Coins[j]。最后1 行是要找的钱数m。

Output
  程序运行结束时,将计算出的最少硬币数输出。问题无解时输出-1。

Sample Input
3
1 3
2 3
5 3
18
Sample Output
5
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2180 today,16258907 total, since 2010-05-07