10212 - The Last Non-zero Digit.

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Feb 03, 2004 12:53 pm

I think 0<=M<=N

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)

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sun Aug 22, 2004 5:17 am

so how does this solution work for finding the last non-zero digit of n!:

[cpp]#include <stdio.h>
#include <string.h>
#define MAXN 1000

long a[MAXN], l;

void a_div_5(void)
{
int i, plus;

plus = 0;
for (i=0; i<l; i++) {
a = a*2+plus;
plus = a/10;
a = a%10;
}
if (plus>0) a[l++] = plus;
l--;
for (i=0; i<l; i++) a = a[i+1];
}

int main(void)
{
char buffer[MAXN];
long mod[20]={1,1,2,1,4,2,2,4,2,3,4,4,3,4,1,3,3,1,3,2};

int result, n, i, plus, j, one;
FILE *f, *g;

f = stdin;
g = stdout;

while ( fscanf(f, "%s", buffer) != EOF) {
l = strlen(buffer);

for (i=0; i<l; i++) a = buffer[l-1-i] - '0';
one = l==1 && a[0]==1;

result = 1;
while (l>0) {
if (l==1) result = result * mod[a[0]] % 5;
else result = result * mod[a[0] + 10*(a[1]%2) ] % 5;
a_div_5();
}

if (one || result%2==0) fprintf(g, "%d\n", result);
else fprintf(g, "%d\n", result+5);

}
return 0;
}
[/cpp]
a_div_5 is obvious, but what is mod??[cpp][/cpp]

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Sat Nov 13, 2004 3:40 pm

dear Riyad
I dont think your code has any chance for getting accepted :wink:

becuase
you want to avoid having 0 by using ,
mult=mult%100000;
which when i> 100000 , for example i=1000000> 20000000 then mult will be 0 and ...
also in your while where x= mult%10, i cant understand why you use a loop, ???

I think the easiest brute force alg is:
S:= 1;
C2:= 0
C5:= 0;
for i:= m+ 1 to n do
j:= i;
while j mod 2= 0 do
j:= j div 2;
Inc (C2);

while j mod 5= 0 do
j:= j div 5;
Inc (C5);
S:= S* (j mod 10);

if C2> C5 then
S:= (S* 2^ (C2- C5) )mod 10
else
S:= (S* 5^ (C5- C2) )mod 10


But I this alg may encounter time limit!
Amir

G
New poster
Posts: 4
Joined: Sun Nov 28, 2004 12:45 pm

10212: Online judge fails

Post by G » Sun Nov 28, 2004 1:03 pm

I solved 10212, but I had some problems with the online judge. If someone supervising the
online judge reads this, then check my submissions numbered 3110597 and 3110602. These
two C programs are essentially the same, except that in one of them I have a "const char *"
having a length 36365 characters (and the online judge says: Wrong Answer), in the other
I broke this string up in a "const char * []", in which every string is of length 220 or less (and
the online judge accepts it). The problem is most likely in the long line, but if I compile these
on my machine, then there is no problem in compiling or running and they give the same answer
for several hundred thousand randomly generated and some special case input. Please,
correct the online judge or the submission method (I do not know which went wrong): I
used the WWW form to submit these programs, and I uploaded the program so there should
not be a copy-paste error in it.

TIA:

Geza

G
New poster
Posts: 4
Joined: Sun Nov 28, 2004 12:45 pm

10212: Online judge fails

Post by G » Wed Dec 01, 2004 8:44 am

I solved 10212, but I had some problems with the online judge. If someone supervising the
online judge reads this, then check my submissions numbered 3110597 and 3110602. These
two C programs are essentially the same, except that in one of them I have a "const char *"
having a length 36365 characters (and the online judge says: Wrong Answer), in the other
I broke this string up in a "const char * []", in which every string is of length 220 or less (and
the online judge accepts it). The problem is most likely in the long line, but if I compile these
on my machine, then there is no problem in compiling or running and they give the same answer
for several hundred thousand randomly generated and some special case input. Please,
correct the online judge or the submission method (I do not know which went wrong): I
used the WWW form to submit these programs, and I uploaded the program so there should
not be a copy-paste error in it.

TIA:

Geza

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

10212 The Last Non-zero Digit

Post by Antonio Ocampo » Sat Dec 04, 2004 12:03 am

Could someone give me a hint ???

I got TLE with my purely force brute algorithm.

Thx in advance... :D

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Fri Mar 18, 2005 5:24 pm

We must factorize n! into this form: 2^i * 3^j * 5^k * 7^l, and find the corresponding i, j, k, and l.

eg, n=10.
10! = 1.2.3.4.5.6.7.8.9.10 = 2^7.3^4.5^2.7^1
and we also know the lastdigit of 2^k, 3^k, 5^k, and 7^k; 0<=k<=p.

If you still confuse how to factorize it, I will gratefull to tell you more...
Also i amm confused of that...
Scorpion
Please would u be a bit more specific :wink:
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

ckm111
New poster
Posts: 2
Joined: Sat Jan 21, 2006 7:36 pm

10212

Post by ckm111 » Sat Jan 21, 2006 7:43 pm

Sorry~~

Can sombody give me test case ~

thanks~~

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Sun Feb 05, 2006 9:22 am

65 8
2

5564 665
2

4445 2222
4

7895 2144
2

10 10
8

54 0
0

0 0
0

87 5
4

545454 66666
4

78965 78956
6

JaviGS
New poster
Posts: 6
Joined: Thu Aug 05, 2004 5:24 pm
Location: Spain

Post by JaviGS » Wed Aug 16, 2006 1:58 am

You're Wrong. Output for cases n 0 should be 1 instead of 0.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Jun 16, 2007 5:45 pm

I am getting WA.. I need a lot of inputs and outputs
Can any one help me..

Code: Select all

CODE removed after getting accepted
or can any one tell me for which input my program produces wrong output?

thanks

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Tue Jun 19, 2007 5:09 am

I'm geting WA.
pleeze tell me my code bug.

Code: Select all

#include <stdio.h>

int n, m, i, a, x;

int main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		a = 1;
		for (i = n-m+1; i <= n; i++)
		{
			a *= i;
			while (a % 10 == 0) a /= 10;
			a %= 10;
		}
		printf("%d\n", a);
	}
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Jun 19, 2007 5:49 am

Integer Overflow

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Tue Jun 19, 2007 6:03 am

I used "long long" but I got TLE

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jun 19, 2007 6:06 am

emotional blind wrote:Integer Overflow
I don't think so.

hamedv, try N=126 M=2. Compute the right answer by hand and compare with your program's output.

Post Reply

Return to “Volume 102 (10200-10299)”