LASTDIG - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem can be solved using dynamic programming, however a more sophisticated solution exists. Denote C(N) as the sum of D(N) over all values from 0 to N-1 (inclusive). Our goal is to calculate C(B+1)-C(A). Note that the first 10 values of D(N) are 0, 1, 4, 3, 8, 5, 2, 7, 6, 9. Each number from 0 to 9 appears exactly once. Also note that D(10 * k + i) = (D (k)+D(i)) % 10, where 0≤i<10. It follows that each number from 0 to 9 will also appear exactly once in D(10 * k + i) as i ranges from 0 to 9 and k is fixed. Therefore, C(10 * k)=45 * k for all k. This allows us to compute C(N) quickly by using C(N) = 45 * N/10 if N is a multiple of 10, and C(N) = C(N-1) + D(N-1) if N is not a multiple of 10.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

10 Likes

#include<stdio.h>
int last(int);
main()
{
short unsigned int w,t=0,p;
unsigned int m,n,i;
scanf("%u",&w);
for(p=1;p<=w;p++)
{
t=0;
scanf("%u%u",&m,&n);
for(i=m;i<=n;i++)
{
t=(last(i)%10)+t;

	}
	printf("%d \n",t);}
	
}
int last(int i)
{
	short unsigned int s=0,j;
	
	while(i!=0)
	{
		j=i%10;
		if(j%2==0)
		s=s+(2*j);
		else s=s+j;
		i=i/10;

	}
	return s;
}

Please always add some text, not only the code. Also it it good to format the code. Probably you wanted to ask why you are getting TLE, simply because you want to perform 400 billions of operations in a second…

1 Like

can any1 explain it with example?

How it can be solved using dp??

here is python code
can anyone tell me where i am wrong

cook your dish here

t = int(input())
sum = 0
for i in range(1,t+1):
a , b = map(int, raw_input().split())
for j in range(a,b+1):
temp =j
while temp > 0:
rem = temp 10 if (rem 2) == 0:
sum = sum +(2*rem)
else :
sum = sum + rem
temp = temp//10

           print(sum%10)

#include<stdio.h>
/int power(int ,long long int);
int main(){
int t,a,i;
long long int b;
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d %lld",&a,&b);
printf("%d\n",power(a,b));
}
return 0;
}
int power(int b,long long int e){
if(e==0)
return 1;
if(e%2==1){
return ((b%10)
(power((bb),(e/2))%10))%10;
}
if(e%2==0){
return (power((b
b),(e/2)))%10;
}
}gives wrong ans in spoj why plz help

//