当前位置:编程学习 > C/C++ >>

URAL 1233 - Amusing Numbers

首先计算出k至少为第几位,如果m小于这个数,那么输出0

还有一种情况, 就是10的i次方的这种情况,如果i+1等于m,那么直接输出k,否则输出0

其他的情况,就是二分,然后判断计算其插入到k之前的数的个数与k至少的位数之和

 

#include <stdio.h>   
#include <math.h>   
#define LL unsigned long long   
  
LL d[20],k,m,s;  
int t;  
void init()  
{  
    d[0]=1;  
    for(int i=1;i<20;i++)  
        d[i]=d[i-1]*10;  
}  
  
int check(LL x)  
{  
    int t=log10(x)+1;  
    if(x/d[t-1]==1&&x%d[t-1]==0&&t<m)return 1;  
    return 0;  
}  
  
LL pre(LL x)  
{  
    LL ans=0;  
    for(int i=0;i<t;i++)  
    {  
        ans+=(x/d[t-1-i]-d[i]+1);  
    }  
    return ans;  
}  
  
LL f(LL x,LL y)  
{  
    LL ans=s;  
    int p=log10(y)+1;  
    for(int i=t+1;i<=p;i++)  
    {  
        if(i<p)  
            ans+=x*d[i-t]-d[i-1];  
        else  
        {  
            if(x*d[i-t]-d[p-1]>y-d[p-1]){ans+=y-d[p-1];}  
            else {ans+=x*d[i-t]-d[p-1];}  
        }  
    }  
    return ans;  
}  
  
int main()  
{  
    scanf("%I64u%I64u",&k,&m);  
    init();  
    t=log10(k)+1;  
    s=pre(k);  
    if(m<s)  
    {  
        printf("0\n");  
    }  
    else  
    {  
        if(check(k))printf("0\n");  
        else  
        {  
            LL l=k,r=1LL<<63,mid=(l+r)/2;  
            while(l<r)  
            {  
                if(f(k,mid)<m) l=mid+1;  
                else r=mid;  
                mid=(l+r)/2;  
            }  
            if(mid==k)  
            printf("%I64u\n",mid);  
            else  
            printf("%I64u\n",mid-1);  
        }  
    }  
    return 0;  
}  

#include <stdio.h>
#include <math.h>
#define LL unsigned long long

LL d[20],k,m,s;
int t;
void init()
{
    d[0]=1;
    for(int i=1;i<20;i++)
        d[i]=d[i-1]*10;
}

int check(LL x)
{
    int t=log10(x)+1;
    if(x/d[t-1]==1&&x%d[t-1]==0&&t<m)return 1;
    return 0;
}

LL pre(LL x)
{
    LL ans=0;
    for(int i=0;i<t;i++)
    {
        ans+=(x/d[t-1-i]-d[i]+1);
    }
    return ans;
}

LL f(LL x,LL y)
{
    LL ans=s;
    int p=log10(y)+1;
    for(int i=t+1;i<=p;i++)
    {
        if(i<p)
            ans+=x*d[i-t]-d[i-1];
        else
        {
            if(x*d[i-t]-d[p-1]>y-d[p-1]){ans+=y-d[p-1];}
            else {ans+=x*d[i-t]-d[p-1];}
        }
    }
    return ans;
}

int main()
{
    scanf("%I64u%I64u",&k,&m);
    init();
    t=log10(k)+1;
    s=pre(k);
    if(m<s)
    {
        printf("0\n");
    }
    else
    {
        if(check(k))printf("0\n");
        else
        {
            LL l=k,r=1LL<<63,mid=(l+r)/2;
            while(l<r)
            {
                if(f(k,mid)<m) l=mid+1;
                else r=mid;
                mid=(l+r)/2;
            }
            if(mid==k)
            printf("%I64u\n",mid);
            else
            printf("%I64u\n",mid-1);
        }
    }
    return 0;
}


 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,