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++ ,