POJ 2591 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]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.