首页 > 代码库 > nyoj 1172 unlucky number

nyoj 1172 unlucky number

unlucky number

时间限制:1000 ms  |  内存限制:65535 KB
难度:0
描述
我们定义在区间【l,r】之间只出现1和7组合的数是unlucky number,例如:1 、7、 11、17 都是unlucky numbers ,而 13 、27则不是,问在区间【l,r】内有多少 unlucky numbers??
输入
有多组测试数据(不超过100组)
每组输入两个整数l,r( 0 =< l<= r <= 10^18)
输出
每行输入一个结果
样例输入
1 7
样例输出
2
上传者

ACM_张书军

思路:和丑数思路一样 用前面的数便利出后面的数 

打个表

然后判断l,r在表中的位置,统计unlucky numbers就行了

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[1000000];
int c;
void init()
{
    c=0;
    a[c++]=1;
    a[c++]=7;
    int k=0;
    while(a[c-1]<1e18)
    {
        a[c++]=a[k]*10+1;
        a[c++]=a[k]*10+7;
        k++;
    }
}
int main()
{
    init();
    long long l,r;
    while(cin>>l>>r)
    {
        int L=0,R=0;
        for(int i=0; i<c; i++)
        {
            if(a[i]<=l) L=i;
            if(a[i]>r)
            {
                R=i;
                break;
            }
        }
        if(a[L]==l||l==0) L--;
        printf("%d\n",R-L-1);
    }
}
        



nyoj 1172 unlucky number