1 10 100 1000

1 10 100 1000

时间： 1ms        内存：128M

描述：

1,10,100,1000...组成序列1101001000...，求这个序列的第N位是0还是1（自左向右）。

输入：

第一行一个整数T，表示数组组数
后面T行，每行一个整数N  (N<=10^9)

输出：

共T行，如果该位是0，输出0;如果该位是1，输出1

示例输入：

3
1
2
3

示例输出：

1
1
0

提示：

参考答案（内存最优[1116]）：

#include <stdio.h>
#include <string.h>
#include <math.h>
int main(){
    int num,n,i=0,j=1,m,mun;
    int a[20000];
    a[0]=1;
    for(i=1;i<20000;i++){
        a[i]=a[i-1]+j;
        j+=1;
    }
    i=0;
    scanf("%d",&num);
    int b[num];
    while(i<num){
        scanf("%d",&b[i]);
        i++;
    }
    i=0;
    while(i<num){
        for(m=0;m<20000;m++){
            mun=b[i];
            if(mun==a[m]){
                printf("1");
                break;
            }else if((mun>a[m])&&(mun<a[m+1]))
            {
                printf("0");
                break;
            }else{
            }
        }
        i++;
        if(i<num){
            printf("\n");
        }
    }

    return 0;
}

参考答案（时间最优[3]）：

#include <stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn],len;
int main()
{
    for (int i=1,num=1;num<=1e9;i++) {   
        a[len++]=num;
        num+=i;
    }
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        int idx=lower_bound(a,a+len,n)-a;
        if (a[idx]==n) 
            printf("1\n");
        else 
            printf("0\n");
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。