10162 - Last Digit

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10162 - Last Digit

Post by 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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

P Last Digit

Post by 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 :lol: [/u]
Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion »

Sorry,

The last line of the input should be 0.
:lol:
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Thanks, clear me up.. I was only keeping track of the first 10 last digits.. should've kept 20..
novice
New poster
Posts: 3
Joined: Tue Jan 07, 2003 10:51 pm

10162

Post by 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;

}
[c][/c]
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

I only made this post a few days ago...
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

10162 (Last Digit) WA [Resolved]

Post by 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!
Last edited by UFP2161 on Fri Aug 01, 2003 12:33 am, edited 2 times in total.
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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?
Last edited by UFP2161 on Wed Aug 06, 2003 11:06 pm, edited 1 time in total.
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Did you forget a

Code: Select all

l = strlen( s )
?
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
New poster
Posts: 8
Joined: Sun Sep 14, 2003 11:38 pm
Location: Dhaka
Contact:

why wa ?

Post by 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]
There is Nothing, Nothing At All !
Ashique Mahmood Rupam
New poster
Posts: 8
Joined: Sun Sep 14, 2003 11:38 pm
Location: Dhaka
Contact:

still WA

Post by Ashique Mahmood Rupam »

What should be done when your sample input output matches but still I get WA ?
There is Nothing, Nothing At All !
Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by 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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

10162 Last Digit WA!!!!!

Post by 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;
}
Post Reply

Return to “Volume 101 (10100-10199)”