POJ 2081 - Recaman's Sequence

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

概要

Recaman 数列を

• \(a_0 = 0\)
• \(a_m = a_{m-1} - m\) (\(a_{m-1} - m > 0\) かつ \(a_{m-1} - m\) がここまでの要素に現れないとき)
• \(a_m = a_{m-1} + m\) (otherwise)

と定める。 与えられた \(k\) について、\(a_k\) を答える。

制約

• \(0 \le k \le 5 \cdot 10 ^ 5\)

解法

事前計算してやるだけ。

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   static const int N = 500000;
 9   static int a[N+1];
10   set<int> seen;
11   seen.insert(0);
12   for (int i = 1; i <= N; i++) {
13     const int x = a[i-1] - i;
14     if (x > 0 && !seen.count(x)) {
15       a[i] = x;
16     } else {
17       a[i] = a[i-1] + i;
18     }
19     seen.insert(a[i]);
20   }
21 
22   for (int k; cin >> k && k != -1;) {
23     cout << a[k] << endl;
24   }
25   return 0;
26 }