Как-то так:
int S0[37],S1[37],S2[37],S3[37],S4[37];
void Expand(int *a,int *b,int n){
int s0=0;
for(int i=0;i<n+10;i++){
if(i<n) s0+=a[i];
if(i>=10) s0-=a[i-10];
b[i]=s0;
}
}
int Conv(int *S,int balance,int m){
int res=0;
while(--m>=0) res+=S[m]*S4[balance+m];
return res;
}
// number of tickets in 0..u-1
int NHappy(int u){
int res=0;
int balance=0;
int digit;
digit=u/10000000; u%=10000000;
for(int i=0;i<digit;i++) res+=Conv(S3,balance++,28);
digit=u/1000000; u%=1000000;
for(int i=0;i<digit;i++) res+=Conv(S2,balance++,19);
digit=u/100000; u%=100000;
for(int i=0;i<digit;i++) res+=Conv(S1,balance++,10);
digit=u/10000; u%=10000;
for(int i=0;i<digit;i++) res+=S4[balance++];
digit=u/1000; u%=1000;
for(int i=0;i<digit && balance>=0;i++) res+=S3[balance--];
digit=u/100; u%=100;
for(int i=0;i<digit && balance>=0;i++) res+=S2[balance--];
digit=u/10; u%=10;
for(int i=0;i<digit && balance>=0;i++) res+=S1[balance--];
if(balance>=0 && balance<u) res++;
return res;
}
void __cdecl main(){
S0[0]=1;
Expand(S0,S1,10);
Expand(S1,S2,19);
Expand(S2,S3,28);
Expand(S3,S4,37);
int m,n;
for(;;){
printf("m,n: ");
scanf("%d%d",&m,&n);
printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
}
}
Проверок входных данных не делается. На простых тестах результаты были правильными. Работает, по моим оценкам, быстрее, чем за 2000 операций. Если нужно проверять много диапазонов, то можно предварительно вычислить частичные суммы Conv() в циклах, и тогда любой диапазон сосчитается за два десятка операций (и при этом не будет требовать гигабайта памяти).
UPD: Вот оптимизированный вариант:
int S[8][38];
void InitS(){
for(int i=1;i<38;i++) S[0][i]=1;
for(int a=1;a<9;a++){
int s0=0;
for(int i=1;i<=37;i++){
s0+=S[a-1][i];
if(i>10) s0-=S[a-1][i-10];
S[a][i]=s0;
}
}
}
// number of tickets in 0..u-1
int NHappy(int u){
int res=0;
int balance=36;
for(int a=7,b=10000000;a>=0;a--,b/=10){
int digit=u/b;
u%=b;
int b1;
if(a>3){
balance-=9;
res+=S[a][b1=balance+digit]-S[a][balance];
} else{
b1=balance-digit; if(b1<0) b1=-1;
res+=S[a][balance+1]-S[a][b1+1];
}
balance=b1;
}
return res;
}
void __cdecl main(){
InitS();
int m,n;
for(;;){
printf("m,n: ");
scanf("%d%d",&m,&n);
printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
}
}
Не спрашивайте, почему :)
Простой
Простой
