POJ 2591 Set Definition（我的水题之路—

POJ 2591 Set Definition（我的水题之路——又一个丑数）

阅读量：4069 次

发布时间：2019-05-25

本文共 1245 字，大约阅读时间需要 4 分钟。

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

Sample Output

Source

,Static

一个集合，里面如果一个元素n，则2*n+1和3*n+1也属于这个集合，这个集合从小到大排列，现在输入一个数字n，问集合中第n个数字的值是多少？

开了一个int的10^7的数组，打表求值，因为要让数组元素从小到大，借用了丑数的计算方法，方法详解说明见：

代码（1AC）：

#include 
    
     #include 
     
      #include 
      
       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]);    }}