| 题目名称 | 2058. 货币问题 |
|---|---|
| 输入输出 | cash_problem.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Skyo
于2015-10-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：4， 通过率：25% | ||||
 Skyo |
100 | 1.565 s | 0.69 MiB | C++ |
 Satoshi |
50 | 0.357 s | 10.23 MiB | C++ |
|
Satoshi |
50 | 0.609 s | 96.06 MiB | C++ |
|
Satoshi |
0 | 0.402 s | 9.85 MiB | C++ |
| 关于 货币问题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
文件名不能用_啊。。。。。。
 waijsf
2015-10-11 06:33
2楼
| ||||
|
完全背包50分，满足了
Satoshi
2015-10-10 17:46
1楼
| ||||
【题目描述】
一套货币体系设计的是否合理的一个重要指标就是能否表示出所有可行的面值。就比如说人民币，因为有{1,2,5,10,100}(元)的存在，所以人民币可以表示所有的整数元。但是并不是所有的货币体系都是合理的，假设某 种货币只包含{3,4}，那么它无论如何也表示不出1,2,5(但是其他的正整数都是能凑出的)，感兴趣的人 可能想要试图分析一套货币体系中到底有多少个正整数数值无法被表示。
【输入格式】
第一行一个正整数 N，表示该货币体系中包含多少种面值(可能重复) 第二行 N 个正整数描述每种面值的具体数值
【输出格式】
若有无穷多个数值无法被表示，则输出”INF”(不含括号) 否则输出一个非负整数解释具体有几个数值无法被表示
【样例输入】
2 3 4
【样例输出】
3
【提示】
对于 20%的数据，N<=10，面值≤100。
对于另外 30%的数据，N<=100，面值≤10000，面值在范围内近似均匀分布(完全随机)。
对于 100%的数据，N<=10^5，面值≤10^9(为避免答案过大，保证至少存在一个面值≤1000)。