POJ 2591 - Set Definition

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

概要

集合 S を

• 1 ∈ S
• x ∈ S ならば，2x+1 ∈ S，3x+1 ∈ S
• S は以上を満たす最小の集合

と定め，S の要素を昇順に並べたときの N 番目の要素を答える．

制約

• 1 <= N <= 10000000

解法

POJ 1338 - Ugly Numbers と同じようにして具体的に S を作って答える．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main(void)
 6 {
 7   static const int N = 10000000;
 8   vector<int> v(N);
 9   int a = 0, b = 0;
10   v[0] = 1;
11   for (int i = 1; i < N; i++) {
12     int x = min(2*v[a]+1, 3*v[b]+1);
13     if (x == 2*v[a]+1) {
14       a++;
15     }
16     if (x == 3*v[b]+1) {
17       b++;
18     }
19     v[i] = x;
20   }
21 
22   int n;
23   while (cin >> n) {
24     cout << v[n-1] << endl;
25   }
26   return 0;
27 }