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;
}

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