GCJに向けて本気で問題を解説してみる 第2回 (Ohgas’ Fortune)
前回に引き続きACM/ICPC国内予選突破ページに紹介されている過去問を全力で解説します。参考ページは
http://www.deqnotes.net/acmicpc/
になります。今回は第2回目の「Ohgas’ Fortune」という問題。僕はAOJでやっているのでAOJのリンクを貼っておきます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1135
この問題は利息の計算をシミュレーションする問題。注意するべきと思われるポイントは次の2つ。
- 問題文だと若干分かりづらいが、単利と複利が途中で入れ替わることはなく、どちらかで指定年数運用することを考える
- 利息および現在の残高は整数の範囲で計算され、年ごとに小数点以下は切り捨てられる
ここに気を付ければ、おそるるに足らない問題です。さっそく正解のコードを載せておきます。
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
int m, y, p, c, n;
ll f;
double r;
int main() {
cin >> m;
rep(t,m) {
cin >> f >> y >> n;
ll ans = 0;
rep(i,n) {
cin >> p >> r >> c;
ll b = f;
if(p == 0) {
ll a = 0;
rep(k,y) {
a += (ll)(b * r);
b -= c;
}
b = a + b;
} else {
rep(k,y) {
b = (ll)(b * (1.0 + r) - c);
}
}
if(b > ans) {
ans = b;
}
}
printf("%lld\n", ans);
}
}
このコードでは念のため利息がかかる金額fをlong long型にしていますが、問題文上intでも通ります。