3721 - 集合
时间限制 : 1 秒
内存限制 : 128 MB
一个集合有如下元素：1是集合元素；若p是集合的元素，则2*p+1和4*p+5也是集合元素。这个集合总是从小的数在前大的数在后。现在想知道集合中第n个元素是多少
题目输入
有多个输入数据，每个输入占一行，为一个数n（1<n<200000）
题目输出
每个输出占一行，为该集合中的第n个元素。
输入/输出样例
输入格式
1 2 3 4
输出格式
1 3 7 9
C语言解答
#include<stdio.h> int main() { int n,i,j=1,k=1,x[200000]={0,1},m; for(i=2;i<=200000;i++) { m=2*x[j]+1; n=4*x[k]+5; if(m>n){x[i]=n;k++;}else{x[i]=m;j++;} } while(scanf("%d",&n)==1) printf("%d\n",x[n]); return 0; }
C++解答
#include <bits/stdc++.h> using namespace std; #define maxn 200005 int d[maxn]; int main() { int index1=0,index2=0; int num=1; d[0]=1; while(num<maxn){ int b1=d[index1]*2+1; int b2=d[index2]*4+5; if (b1<=b2){ d[num++]=b1; index1++; } else d[num++]=b2,index2++; } int n; while(~scanf("%d",&n)){ printf("%d\n",d[n-1]); } return 0; }