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
", arr[n]); } }

좋은 웹페이지 즐겨찾기