UVA-11308(法則)
悲しいですね.debugは一晩中、主に最初に数字を分割したとき、間違っていました.
テーマの構想は、最高位から順番に数字を確定する.テンプレート列を構成する;
テーマの構想は、最高位から順番に数字を確定する.テンプレート列を構成する;
#include <cstdio>
#include <set>
#include <cstring>
#include <cctype>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
long long c[11];
long long d[11];
int Bit(long long x){
int cnt=0;
while(x>0){
x/=10; cnt++;
}
return cnt;
}
long long solve(long long p){
if(p==1) return 1;
return 9*d[p-1]+solve(p-1);
}
long long cal(long long n,int p,bool is_first){
if(p<=1){
return 1;
}
long long num = n/c[p-1];
long long res = cal(n-num*c[p-1],p-1,false);
if(is_first){
res += (num-1)*(d[p-1]);
res += solve(p-1);
}
else {
res += num*d[p-1];
res += num ==0 ? (n-num*c[p-1]+1) :c[p-1];
}
return res;
}
int main()
{
c[1]= 10;
for(int i=2;i<=10;i++) c[i]=c[i-1]*10;
d[1] = 1;
for(int i=2;i<=10;i++){
d[i]=10*d[i-1]+c[i-1];
}
long long n,m;
while(cin>>n>>m && n>=0){
long long res1 = n==0 ? 0 : cal(n-1,Bit(n-1),true);
long long res2 = cal(m,Bit(m),true);
cout<<(long long)(res2 - res1)<<endl;
}
return 0;
}
void debug(){
int lim = 1091;
char buf[10];
int cnt=0;
for(int i=0;i<=lim;i++){
sprintf(buf,"%d",i);
int len=strlen(buf);
for(int j=0;j<len;j++)
if(buf[j]==48) cnt++;
}
cout<<cal(lim,Bit(lim),true)<<endl;
printf("%d
",cnt);
}