10780 - Again Prime? No Time.

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

Moderator: Board moderators

Teapot
New poster
Posts: 3
Joined: Tue Nov 23, 2004 12:06 pm

10780 - Again Prime? No Time.

Post by Teapot » Tue Nov 23, 2004 12:12 pm

Why WA?

[c]#include <stdio.h>

int getDevidersNumber(int a, int b)
{
int i = 0;
while (0 == (a % b)) {
a = a / b;
i++;
}
return i;
}

int main(void)
{
int i, j, N, m, n, pow;
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d %d", &m, &n);
printf("Case %d:\n", i);
if (n == 1) {
printf("0");
} else {
j = m;
pow = 0;
while (j <= n) {
pow += getDevidersNumber(j, m);
j += m;
}
if (pow) {
printf("%d", pow);
} else {
printf("Impossible to divide");
}
}
printf("\n");
}
return 0;
}[/c]

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Tue Nov 23, 2004 3:23 pm

If N equals 1, you should output Impossible to divide, as M clearly doesn't divide 1!=1. I'm not going to check the rest of your code (and I doubt that too many people here are willing to do it). The next time please explain the ideas behind your algorithm instead of posting the source.

Teapot
New poster
Posts: 3
Joined: Tue Nov 23, 2004 12:06 pm

Post by Teapot » Tue Nov 23, 2004 9:23 pm

Ok. Thanks for your help.
I did not describe idea, because I thought it's pretty simple.
I've used the definition of a factorial.
I check numbers from m to n with step m. And calculate number of dividers equal m (a power of m). Then I add these numbers. Resulting sum is the largest power of m.

It is written in my code:
[c] while (j <= n) {
pow += getDevidersNumber(j, m);
j++;
}[/c]
I have corrected the program according to your tips, but I still receive WA.

Corrected program:
[c]#include <stdio.h>

int getDevidersNumber(int a, int b)
{
int i = 0;
while (0 == (a % b)) {
a = a / b;
i++;
}
return i;
}

int main(void)
{
int i, j, N, m, n, pow;
scanf("%d", &N);
for (i = 1; i <= N; i++) {
scanf("%d", &m);
scanf("%d", &n);
printf("Case %d:\n", i);
j = m;
pow = 0;
while (j <= n) {
pow += getDevidersNumber(j, m);
j += m;
}
if (pow) {
printf("%d", pow);
} else {
printf("Impossible to divide");
}
printf("\n");
}
return 0;
}[/c]

I do not understand what is wrong. Can you give me some test cases?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Nov 23, 2004 9:56 pm

Teapot wrote:I did not describe idea, because I thought it's pretty simple.
Reading somebody's code is never easy. Please don't post source code only without any idea explained.

I didn't read your code thoroughly, but your idea is wrong.
At least it will fail for the input 10 9. The correct output is 1.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Wed Nov 24, 2004 11:48 am

How about the input/output?

in:

9
3123 2342
234 2343
45 789
111 2222
4999 9999
4999 2
23 6324
454 9022
223 45

out:
Case 1:
6
Case 2:
194
Case 3:
195
Case 4:
61
Case 5:
2
Case 6:
Impossible to divide
Case 7:
285
Case 8:
39
Case 9:
Impossible to divide

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Wed Nov 24, 2004 12:23 pm

I got ac....

Teapot
New poster
Posts: 3
Joined: Tue Nov 23, 2004 12:06 pm

Post by Teapot » Wed Nov 24, 2004 1:39 pm

Thanks a lot guys! I got AC now.

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

10780 .. Again Prime? No Time.

Post by muvee » Tue Nov 30, 2004 10:02 pm

I'm getting WA .. I've tested the test cases in another thread and they all work. Can you give you your output for these cases and if mine are all correct can you please suggest some other test cases. Thanks.

Input:

Code: Select all

7
4500 3
3 4500
4999 9999
2 9999
2 2
5 5
10 10

Output:

Code: Select all

Case 1:
Impossible to divide
Case 2:
2247
Case 3:
2
Case 4:
9991
Case 5:
1
Case 6:
1
Case 7:
2

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Tue Nov 30, 2004 11:09 pm

Here are some further test cases i ran it on.

Input:
50
104 6077
3074 4949
3539 4793
79 6508
3003 5955
2896 8979
2937 3527
629 2235
1017 1573
1844 6419
4911 3829
2041 2358
606 5888
4069 4074
2977 3994
4698 105
2318 8681
1061 7514
1959 4096
733 7567
2947 7851
4684 4680
269 9859
268 1860
2851 9715
547 6972
1730 5320
2906 3082
759 5719
4770 9985
2745 1485
472 5896
358 6460
3315 25
1779 5057
3931 8435
2216 3825
868 4101
3554 3584
4852 3795
259 8733
2745 8034
119 6199
3286 3713
4569 2111
4280 2933
4310 6547
284 1660
599 5714
299 1510
Output:
Case 1:
504
Case 2:
94
Case 3:
1
Case 4:
83
Case 5:
495
Case 6:
49
Case 7:
39
Case 8:
61
Case 9:
13
Case 10:
13
Case 11:
2
Case 12:
15
Case 13:
58
Case 14:
13
Case 15:
17
Case 16:
3
Case 17:
144
Case 18:
7
Case 19:
6
Case 20:
10
Case 21:
18
Case 22:
3
Case 23:
36
Case 24:
27
Case 25:
3
Case 26:
12
Case 27:
30
Case 28:
2
Case 29:
258
Case 30:
191
Case 31:
24
Case 32:
100
Case 33:
36
Case 34:
1
Case 35:
8
Case 36:
2
Case 37:
13
Case 38:
136
Case 39:
2
Case 40:
3
Case 41:
242
Case 42:
133
Case 43:
386
Case 44:
71
Case 45:
1
Case 46:
27
Case 47:
15
Case 48:
23
Case 49:
9
Case 50:
67

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Dec 01, 2004 9:45 am

My AC code gives the same output as yours.
Let's try some boundary cases:

Code: Select all

115
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
4995 9995
4995 9996
4995 9997
4995 9998
4995 9999
4996 9995
4996 9996
4996 9997
4996 9998
4996 9999
4997 9995
4997 9996
4997 9997
4997 9998
4997 9999
4998 9995
4998 9996
4998 9997
4998 9998
4998 9999
4999 9995
4999 9996
4999 9997
4999 9998
4999 9999
My output:

Code: Select all

Case 1:
Impossible to divide
Case 2:
1
Case 3:
1
Case 4:
3
Case 5:
3
Case 6:
4
Case 7:
4
Case 8:
7
Case 9:
7
Case 10:
8
Case 11:
Impossible to divide
Case 12:
Impossible to divide
Case 13:
1
Case 14:
1
Case 15:
1
Case 16:
2
Case 17:
2
Case 18:
2
Case 19:
4
Case 20:
4
Case 21:
Impossible to divide
Case 22:
Impossible to divide
Case 23:
Impossible to divide
Case 24:
1
Case 25:
1
Case 26:
2
Case 27:
2
Case 28:
3
Case 29:
3
Case 30:
4
Case 31:
Impossible to divide
Case 32:
Impossible to divide
Case 33:
Impossible to divide
Case 34:
Impossible to divide
Case 35:
1
Case 36:
1
Case 37:
1
Case 38:
1
Case 39:
1
Case 40:
2
Case 41:
Impossible to divide
Case 42:
Impossible to divide
Case 43:
1
Case 44:
1
Case 45:
1
Case 46:
2
Case 47:
2
Case 48:
2
Case 49:
4
Case 50:
4
Case 51:
Impossible to divide
Case 52:
Impossible to divide
Case 53:
Impossible to divide
Case 54:
Impossible to divide
Case 55:
Impossible to divide
Case 56:
Impossible to divide
Case 57:
1
Case 58:
1
Case 59:
1
Case 60:
1
Case 61:
Impossible to divide
Case 62:
Impossible to divide
Case 63:
Impossible to divide
Case 64:
1
Case 65:
1
Case 66:
1
Case 67:
1
Case 68:
2
Case 69:
2
Case 70:
2
Case 71:
Impossible to divide
Case 72:
Impossible to divide
Case 73:
Impossible to divide
Case 74:
Impossible to divide
Case 75:
Impossible to divide
Case 76:
1
Case 77:
1
Case 78:
1
Case 79:
2
Case 80:
2
Case 81:
Impossible to divide
Case 82:
Impossible to divide
Case 83:
Impossible to divide
Case 84:
Impossible to divide
Case 85:
1
Case 86:
1
Case 87:
1
Case 88:
1
Case 89:
1
Case 90:
2
Case 91:
277
Case 92:
277
Case 93:
277
Case 94:
277
Case 95:
277
Case 96:
8
Case 97:
8
Case 98:
8
Case 99:
8
Case 100:
8
Case 101:
38
Case 102:
38
Case 103:
38
Case 104:
38
Case 105:
38
Case 106:
623
Case 107:
624
Case 108:
624
Case 109:
624
Case 110:
624
Case 111:
1
Case 112:
1
Case 113:
1
Case 114:
2
Case 115:
2

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Wed Dec 01, 2004 11:14 am

Thanks Cho! I got AC. I had made a couple of silly mistakes.

My AC has a time for 0.9 seconds.. I was wondering what yours was because I can see some people have done this problem in 0.02 seconds ! If yours is also low, can you please give me some hints on your algorithm?

Thanks.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Dec 01, 2004 11:34 am

My code takes 0.004s.
I preprocess an array factor[] such that factor is storing the greatest prime factor of i.
Then for any m, I find the prime factorization of m. This is easily done in worst case log(m) time by making use of factor[].
For each of m's distinct prime factor p, let a_p = # of factor p in n! / # of factor p in m. # of factor p in n! can be solved by a simple recursive function in log(n) time.
The minimum a_p among all prime factor p of m is the output. And the running time is O(log(m)*log(n))

muvee
New poster
Posts: 25
Joined: Sun Sep 05, 2004 12:41 am

Post by muvee » Wed Dec 01, 2004 3:54 pm

Thanks Cho.

That is exactly what I did except I did it quite inefficiently!

Thanks again for all your help.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Dec 16, 2004 2:53 pm

My algo is as follows:
1. find all primes in [1, 10000]
2. for given (m, n)
a. find prime pk such that m = p1^q1...pk^qk, p1<p2<...<pk
b. find the max power of pk that divides n!
c. find the max power of pk that divides m
3. ans = res of step b / res of step b

Am I wrong?

Suman.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu Dec 16, 2004 3:22 pm

How have you calculated ??
b. find the max power of pk that divides n!
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Post Reply

Return to “Volume 107 (10700-10799)”