## 10212 - The Last Non-zero Digit.

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
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
I dont think your code has any chance for getting accepted

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

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

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

Could someone give me a hint ???

I got TLE with my purely force brute algorithm.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
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
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

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
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
You're Wrong. Output for cases n 0 should be 1 instead of 0.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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
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);
}
}
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Integer Overflow

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 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:
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.