10162 - Last Digit

[Larry]

I keep getting WA, but I think I have the right concept, can someone give me some input/output?

Basically my algorithm is this: I calculate how long until a cycle occurs, which is 100 in this case. Then I read in the number and mod it by 100, and check the array.

I've realize it needs big int, and took care of that too...

[Red Scorpion]

[/pre]
Hi, Larry
Try This sample I/O:

Sample Input :
999
1000231
2000000000000000000000000000000000000000000000000000000000000
1020030010300130010301000
991919921999
19129399999999999999999999999999999999999995193395919359919599931599591995
95959595959595959595959595959595
99130132
20
1
7
3939528501853018609318903680917609817906091809581098609381908509710976509176124125

Sample Output:
0
2
0
0
0
4
4
8
4
1
2
7

Hope this helps.
[pre]

GOOD LUCK,
RED SCORPION [/u]

[Red Scorpion]

Sorry,

The last line of the input should be 0.

[Larry]

Thanks, clear me up.. I was only keeping track of the first 10 last digits.. should've kept 20..

[novice]

I have wrong answer.Who can help me.
my code is here in C


#include<stdio.h>
#include<string.h>


int last_digit(int m,int n,int num [9]);


void main()
{
char *s;
unsigned long l;
int b,last,i,c;
int odd[9] = { 1,4,7,6,5,6,3,6,9 };
int even[9] = { 1,6,3,6,5,6,7,4,9 };

freopen("last_dgt.in","r",stdin);
// freopen("last_dgt.out","w",stdout);




while(gets(s))
{
if(!(*s))
break;

l=strlen(s);

if(l==1 && s[0]=='0')
break;


if(l>=2)
b=s[l-2]-'0';
else
b=0;

c=s[l-1]-'0';

if(!b && !c)
last = 0;

else
{
if(b%2)
last = last_digit(b,c,even);
else
last = last_digit(b,c,odd);
}

printf("%d\n",last);

}
fclose(stdin);
fclose(stdout);



}

int last_digit(int m,int n,int num[9])
{
int i,s=0;

for(i=0;i<n;i++)
s += num;
i=7*m;
s+=i;

return s%10;

}

Code: Select all

[c][/c]

[Larry]

http://acm.uva.es/board/viewtopic.php?t ... ight=10162

I only made this post a few days ago...

[UFP2161]

Could someone give me the correct output to the following input?

89762189721154078504117545351837972799414006058900
46328348474947111121683585242921341680071269527347
31138733670953297257902064864620098214836159891771
83682586533502351448054917906401463655436160031888
80266228272859746231675378939757365731355870072734
57877387351815771847886863464333778126118820201428
30572606006261629550098990519140091317219098064753
30295026976940778299614225626424594046819247212283
38927084980140140325534872360459046228911029496600
39693271478251874369067809163690608419609752663258
39619632913263869535719748471326786705111458632493
79132050032400774536909876203149667547411318949834
28509148212608663632614279769615715450184957245439
63905302343360516508603439034775654757949276490302
06006244458977942121667208794317734938832132956327
08346758297235913776397298658762247648644018139157
88547027545359955071822316663286258609509802145478
76621279299368887060213467839065698575048547287348
16667580451677444586782714006278894986365709526529
76954515631464942774381565404303159609059098963691
0

Thanks!

[Dominik Michniewski]

My Acc source gives me this output:

Code: Select all

0
0
0
4
7
2
5
8
0
3
3
7
8
5
6
9
7
6
1
4

Best regards
DM

[UFP2161]

[cpp]-- EDITED OUT --[/cpp]

Basically, check last two digits and output from pre-calculated array of last digits. (The array has been checked for correctness using BigInteger and Java.)

Is there some critical input that it's choking on?

[Larry]

Did you forget a

Code: Select all

l = strlen( s )

?

[UFP2161]

haha.. you're right, for some reason, I thought I only had one 'l' (ell) in my program, so I changed it to strlen inside to atoi() to save one measly variable... looks like a "1" (one).. next time, I should stick to "len" or something.. heh

Thanks again!

[Ashique Mahmood Rupam]

Any one help me know why this code gets WA...

[cpp]#include <cstdio>
#include <cstring>

int lastDigitOfMPowN( int m, int n )
{
int ld;
int nmod4;

nmod4 = n % 4;

switch ( m ) {

case 0:

ld = 0;

break;
case 1:
ld = 1;
break;
case 2:

if ( n == 0 ) {
ld = 1;
} else {
switch ( nmod4 ) {
case 0:
ld = 6;
break;
case 1:
ld = 2;
break;
case 2:
ld = 4;
break;
case 3:
ld = 8;
break;
}
}

break;
case 3:
switch ( nmod4 ) {
case 0:
ld = 1;
break;
case 1:
ld = 3;
break;
case 2:
ld = 9;
break;
case 3:
ld = 7;
break;
}
break;
case 4:
if ( n == 0 ) {
ld = 1;
} else {
switch ( nmod4 % 2 ) {
case 0:
ld = 6;
break;
case 1:
ld = 4;
break;
}
}
break;
case 5:
if ( n == 0 ) {
ld = 1;
} else {
ld = 5;
}
break;
case 6:
if ( n == 0 ) {
ld = 1;
} else {
ld = 6;
}
break;
case 7:
switch ( nmod4 ) {
case 0:
ld = 1;
break;
case 1:
ld = 7;
break;
case 2:
ld = 9;
break;
case 3:
ld = 3;
break;
}
break;
case 8:
if ( n == 0 ) {
ld = 1;
} else {
switch ( nmod4 ) {
case 0:
ld = 6;
break;
case 1:
ld = 8;
break;
case 2:
ld = 4;
break;
case 3:
ld = 2;
break;
}
}
break;
case 9:
switch ( nmod4 % 2 ) {
case 0:
ld = 1;
break;
case 1:
ld = 9;
break;
}
break;
}

return ld;
}

int main( )
{
int n, i;
int len;
char str[110];
int ld;

while ( 1 ) {
scanf( "%s", str );

len = strlen( str );
if ( len == 1 && str[0] == '0' )
break;

n = str[len-1] - '0';

if ( len >= 2 ) {
n = n + ( str[len-2] - '0' ) * 10;
}

ld = 0;
for ( i = 1; i <= n; i++ ) {
if ( i == 98 )
i = i;
ld = ( ld + lastDigitOfMPowN( i%10, i ) ) % 10;
}

printf( "%d\n", ld );

}

return 0;
}

/*
0 1 2 3 4 5 6 7 8 9 10
----------------------------
0 -> 0 if ( m == 0 ) 0
1 -> 1 if ( m == 1 ) 1
2 -> 1 2 4 8 6 2 4 8 6 2 4 n == 0 | n mod 4
3 -> 1 3 9 7 1 3 n mod 4
4 -> 1 4 6 4 6 n == 0 | n mod 2
5 -> 1 5 5 5 5 n == 0 | n > 1
6 -> 1 6 6 6 6 n == 0 | n > 1
7 -> 1 7 9 3 1 n mod 4
8 -> 1 8 4 2 6 8 4 n == 0 | n mod 4
9 -> 1 9 1 9 n mod 2

*/[/cpp]

[Ashique Mahmood Rupam]

What should be done when your sample input output matches but still I get WA ?

[Amir Aavani]

hi dear
i afraid your program has problem with n> 100.
that is correct that i^i= (i+ 100)^ (i+ 100) but note that you want to calculate the sum of this numbers.
so i think you must at first find the last digit of (n div 100) (call it as a) and also n mod 100 (and call it as b). and let c and d be
c:= 0;
for i:= 0 to 99 do
c:=c+ lastDigitOfMPowN( i mod 10, i);

d:= 0;
for i:= 0 to b do
d:=d+ lastDigitOfMPowN( i mod 10, i);

now the result is ((c* a) mod 10+ d) mod 10.
i dont know if c is equal to 0 or not, but if it isn't your program is obviously wrong.

[Chok]

Hi all,
I'm getting wa several times for this problem. My code also passed for all input given by the previous post. Please help me to find out my error.

Code: Select all

#include<stdio.h>
#include<string.h>

#define mem(a,b) memset((a),(b),sizeof(a))

#define MAX 1000

char in1[MAX];

int pcal[9][5];
int len1;

void ini()
{
	mem(pcal,0);
	pcal[1][0]=1;pcal[1][1]=1;
	pcal[2][0]=4;pcal[2][1]=2,pcal[2][2]=4,pcal[2][3]=8,pcal[2][4]=6;
	pcal[3][0]=4;pcal[3][1]=3,pcal[3][2]=9,pcal[3][3]=7,pcal[3][4]=1;
	pcal[4][0]=2;pcal[4][1]=4,pcal[4][2]=6;
	pcal[5][0]=1;pcal[5][1]=5;
	pcal[6][0]=1;pcal[6][1]=6;
	pcal[7][0]=4;pcal[7][1]=7,pcal[7][2]=9,pcal[7][3]=3,pcal[7][4]=1;
	pcal[8][0]=4;pcal[8][1]=8,pcal[8][2]=4,pcal[8][3]=2,pcal[8][4]=6;
	pcal[9][0]=2;pcal[9][1]=9,pcal[9][2]=1;
}

int last_digit(int m,int n)
{
	int index;
	if(n==0 || m==0) 
		return 0;
	else
	{
		index=n%pcal[m][0];
		if(index==0)
			index=pcal[m][0];
		return pcal[m][index];
	}
}

int main()
{
	int c,d,a,b,res,i,tmp;
	//freopen("10162.in","r",stdin);
	//freopen("10162.out","w",stdout);
	ini();
	while(1)
	{
		scanf("%s",in1);
		len1=strlen(in1);
		if(len1==1 && in1[0]=='0')
			break;
		if(len1==1)
			b=in1[len1-1]-'0';
		else if(len1==2)
			b=(in1[len1-2]-'0')*10+(in1[len1-1]-'0');
		else
			b=(in1[len1-3]-'0')*100+(in1[len1-2]-'0')*10+(in1[len1-1]-'0');
		if(len1==1)
			a=(in1[0]-'0');
		else
			a=(in1[0]-'0')*10+(in1[1]-'0');
		a=a/100;
		c=d=0;
		for(i=0;i<=a;i++)
		{
			tmp=last_digit(i%10,i);
			c+=tmp;
		}
		for(i=0;i<=b;i++)
		{
			tmp=last_digit(i%10,i);
			d+=tmp;
		}
		res=((c*a)%10+d)%10;
		printf("%d\n",res);
	}
	return 0;
}