Ohgas' Fortune 解説

アルゴリズムの概略

文章は非常に長いのですが,解法は非常に簡単で,問題文に書かれているように複利や単利の計算をすればOKです。 与えられたそれぞれのケースに対して答えを求め,そのうちの最大値を出力します。 文章を読むのが一番大変なので問題の種類は文章読解です(たまにこういう問題があります)。

アルゴリズムの計算量

提示方法の数 n × 年数 y の係数倍で,O(n×y) になります。 n <= 100, y <= 10 なので,たかだか 1000c の命令数で済みます(c: 定数)。

アルゴリズムの実装

個々の提示方法についての計算結果は保持する必要がなく,単に変数 max を更新していくだけでOKです。 アルゴリズムは,

max = 0
for each 各提示方法:
  結果resultを求める
  if result > max: max = result

となります。

注意点として,int型は最低32ビットあると仮定してもOKです。ですから,long int型を使う必要はありません。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $