POJ 2591 Set Definition（我的水題之路——又一個醜數）

Set Definition

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 8304	Accepted: 3792

Description

Set S is defined as follows: 

(1) 1 is in S; 

(2) If x is in S, then 2x + 1 and 3x + 1 are also in S; 

(3) No other element belongs to S. 

Find the N-th element of set S, if we sort the elements in S by increasing order.

Input

Input will contain several test cases; each contains a single positive integer N (1 <= N <= 10000000), which has been described above.

Output

For each test case, output the corresponding element in S.

Sample Input

100
254
      

Sample Output

418
1461
      

Source

POJ Monthly--2005.08.28,Static

一個集合，裡面如果一個元素n，則2*n+1和3*n+1也屬于這個集合，這個集合從小到大排列，現在輸入一個數字n，問集合中第n個數字的值是多少？

開了一個int的10^7的數組，打表求值，因為要讓數組元素從小到大，借用了醜數的計算方法，方法詳解說明見： POJ1338的解題報告

代碼（1AC）：

#include <cstdio>
#include <cstdlib>
#include <cstring>

int arr[10000100];

void init(){
    int x2, x3;
    int i;

    x2 = x3 = 1;
    arr[1] = 1;
    for (i = 2; i <= 10000000; i++){
        arr[i] = (2 * arr[x2] + 1) < (3 * arr[x3] + 1) ? (2 * arr[x2] + 1) : (3 * arr[x3] + 1);
        if (arr[i] == 2 * arr[x2] + 1){
            x2 ++;
        }
        if (arr[i] == 3 * arr[x3] + 1){
            x3 ++;
        }
    }
}

int main(void){
    int n;

    init();
    while (scanf("%d", &n) != EOF){
        printf("%d\n", arr[n]);
    }
}