A. Optimal Currency Exchange
time limit per test1.5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Andrew was very excited to participate in Olympiad of Metropolises. Days flew by quickly, and Andrew is already at the airport, ready to go home. He has n rubles left, and would like to exchange them to euro and dollar bills. Andrew can mix dollar bills and euro bills in whatever way he wants. The price of one dollar is d rubles, and one euro costs e rubles.
Recall that there exist the following dollar bills: 1, 2, 5, 10, 20, 50, 100, and the following euro bills — 5, 10, 20, 50, 100, 200 (note that, in this problem we do not consider the 500 euro bill, it is hard to find such bills in the currency exchange points). Andrew can buy any combination of bills, and his goal is to minimize the total number of rubles he will have after the exchange.
Help him — write a program that given integers n, e and d, finds the minimum number of rubles Andrew can get after buying dollar and euro bills.
Input
The first line of the input contains one integer n (1≤n≤108) — the initial sum in rubles Andrew has.
The second line of the input contains one integer d (30≤d≤100) — the price of one dollar in rubles.
The third line of the input contains integer e (30≤e≤100) — the price of one euro in rubles.
Output
Output one integer — the minimum number of rubles Andrew can have after buying dollar and euro bills optimally.
Examples
input
100
60
70
output
40
input
410
55
70
output
5
input
600
60
70
output
0
Note
In the first example, we can buy just 1 dollar because there is no 1 euro bill.
In the second example, optimal exchange is to buy 5 euro and 1 dollar.
In the third example, optimal exchange is to buy 10 dollars in one bill.
题意： 给出n卢布，并对应给出一美元可兑换的卢布金额和一欧元可兑换的卢布金额，同时给出了不同的美元面额和欧元面额，问兑换后（可以任意兑换，或同时兑换美元和欧元）， 问最少剩下的卢布值为多少。
思路： 给出的美元面额中，除1以外，其余均为1的倍数；给出的欧元面额中，除5外，其余均为5的倍数，所以不管如何兑换，我们只考虑最小面额，先对一欧元能兑换的金额不断进行累加枚举，再不断一美元能兑换的金额取模更新最小值。详情看代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, d, e;
int a[7] = {1, 2, 5, 10, 20, 50, 100};
int b[6] = {5, 10, 20, 50, 100, 200};
scanf("%d%d%d", &n, &d, &e);
for (int i = 0; i < 7; i++) {
a[i] *= d;
}
for (int i = 0; i < 6; i++) {
b[i] *= e;
}
int ans = 1e9 + 7;
for (int i = 0; i <= n; i += b[0]) { // 对一欧元能兑换的金额进行枚举
ans = min(ans, (n - i) % a[0]); // 对一美元能兑换的金额进行取模
}
printf("%d\n", ans);
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
