POJ 2661 - Factstone Benchmark

http://poj.org/problem?id=2661

概要

Amtel は1960年に4-bitのコンピュータをリリースし，以降10年毎に倍のワード長を持つコピュータをリリースしている．

新しいチップの性能を，n! をそのワード長で符号無し整数として表現できるような最大の n で示している． これを Factstone rating と言う．

y 年における最新のチップでの Factstone rating を答える．

制約

• 1960 <= y <= 2160

解法

実際に階乗を計算して最初にテーブルを作っておいて答えるだけ． double の精度で問題無い．

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int tbl[21];
 8 
 9   for (int i = 0; i < sizeof tbl/sizeof *tbl; i++) {
10     const double k = static_cast<double>(4 << i);
11     double f = 0.0;
12     for (int j = 1;; j++) {
13       f += log(static_cast<double>(j)) / log(2);
14       if (f > k) {
15         tbl[i] = j-1;
16         break;
17       }
18     }
19   }
20 
21   int y;
22   while (cin >> y && y != 0) {
23     cout << tbl[(y-1960)/10] << endl;
24   }
25   return 0;
26 }