2013-09-11 08:39:58Morris
[UVA][dp] 11285 - Exchange Rates
Problem A: Exchange Rates
Now that the Loonie is hovering about par with the Greenback, you have decided to use your $1000 entrance scholarship to engage in currency speculation. So you gaze into a crystal ball which predicts the closing exchange rate between Canadian and U.S. dollars for each of the next several days. On any given day, you can switch some or all of your money from Canadian to U.S. dollars, or vice versa, at the prevailing exchange rate, less a 3% commission, less any fraction of a cent.Assuming your crystal ball is correct, what's the maximum amount of money you can have, in Canadian dollars, when you're done?
The input contains a number of test cases, followed by a line containing 0. Each test case begins with 0 <d ≤ 365, the number of days that your crystal ball can predict. d lines follow, giving the price of a U.S. dollar in Canadian dollars. For each test case, output a line giving the maximum amount of money, in Canadian dollars and cents, that it is possible to have at the end of the last prediction, assuming you may exchange money on any subset of the predicted days, in order.
Sample Input
3 1.05 0.93 0.99 2 1.05 1.10 0
Output for Sample Input
1001.60 1000.00
Ondřej Lhoták
題目描述：
一開始有 1000 元的加拿大幣，接下來會有 n 天幣值表示每 1 加拿大幣可以換多少美金。
而每次轉換手續費是交換金額的 3%，剩餘金額無條件捨去到分(1 元 = 100 分)
問最後手上最多的加拿大幣為何？
題目解法：
O(1) 記憶體空間。
每次交換一定是全部金額進行交換，使用兩個變數表示在第 i 天之前，
曾經手上擁有美金或加拿大幣的最高金額。
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
int n;
while(scanf("%d", &n) == 1 && n) {
int a = 100000, b = 0;
int cost;
double rate;
while(n--) {
scanf("%lf", &rate);
double ta, tb;
tb = a/rate*0.97;
ta = b*rate*0.97;
a = max(a, (int)ta);
b = max(b, (int)tb);
}
printf("%d.%02d\n", a/100, a%100);
}
return 0;
}