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

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

Post by sumankar » Thu Dec 16, 2004 3:59 pm

Sum[floor(n/p^i)] i = 1...k, such that p^(k+1) > n

suman

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

Post by sumankar » Sat Dec 18, 2004 11:37 am

I have umpteen WA's here and I am really really :evil: pissed off with this
problem.My prog o/p matches all i/o given here.It seems I am missing some
stupid little trick.

Any ideas, fellows?

Suman.

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

Post by sumankar » Mon Dec 20, 2004 8:18 am

HI all

Any ideas!!

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Sat Dec 25, 2004 6:46 pm

Hi Suman:

Here is my algo, i hope you find it useful...

1. Find all the primes from 1..5000.
2. For each prime x that divides m find such a1 that m % x^a1 == 0 and a2 that n! % x^a2 == 0, if a1 > a2 then n! is not divided by m else store the minimal a2 / a1 and that is the result. :D

I Hope you solve that!!!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Jan 21, 2005 5:16 am

I think this problem's description is WRONG!!!!
The smallest power of 13 that divides 2! does exist - it is 0.

:evil: :evil: :evil: :evil: :evil: :evil:

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

Post by misof » Fri Jan 21, 2005 3:11 pm

minskcity wrote:I think this problem's description is WRONG!!!!
The smallest power of 13 that divides 2! does exist - it is 0.

:evil: :evil: :evil: :evil: :evil: :evil:
(correction: apparently you meant the greatest power of 13)

No need to be angry, just read the problem statement more carefully. The problem description is correct, as is your (corrected) second sentence. Let's see some quotes:
problem description wrote:Given a number n you have to determine the largest power of m, not necessarily prime, that divides n!.
This is the sentence you are referring to. Basically, this sentence tells you what to do.
output description wrote:The result is either an integer if m divides n! or a line "Impossible to divide" (without the quotes).
This is the output description. After you have solved the problem, this section tells you how to format your output. In my humble opinion, the case "m doesn't divide n!" is exactly the case when the greatest power of m dividing n! is 0. So, this section tells you: instead of zero, output a message. What's wrong with that?

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Jan 21, 2005 5:06 pm

misof wrote:
output description wrote:The result is either an integer if m divides n! or a line "Impossible to divide" (without the quotes).
This is the output description. After you have solved the problem, this section tells you how to format your output. In my humble opinion, the case "m doesn't divide n!" is exactly the case when the greatest power of m dividing n! is 0. So, this section tells you: instead of zero, output a message. What's wrong with that?
For many problems from Valladolid the second option (such as "no solution") never needs to be printed. How do I know that it's not the case here? It is quite clear to me that division is always possible according to problem statement... :roll:

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Feb 16, 2005 11:23 pm

Of course there're cases when you print
"Impossible to divide"

For example what is the highest degree of M=23 which
divides N ! = 5 !

Of course it is 0 so you print "Impossible to divide"

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Thu Feb 17, 2005 11:05 pm

Why exactly am I supposed to print "Impossible to divide" when I can divide by 23^0? Can you give me the sentence in problem statement that says so? My understanding of "impossible to divide" is impossible to divide and not "impossible to divide for the exception of M^0". I see nothing that makes zero special in the problem statement. And if I have to print "impossible to divide" when answer is 0, why should not I print "impossible to divide" when answer is 1, 2, 3....???? :-? :roll:

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Feb 18, 2005 12:44 am

I agree that the problem statement could be clearer. But here is what is meant:
The powers of m are integers values m^p with p a integer >0 (in this problem). So, if there is no such power of m which divides n, you have to print "Impossible to divide".

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

Post by Dominik Michniewski » Wed May 25, 2005 1:07 pm

I have a problem with this problem ;)

My algorithm is:

1. generate primes in range [2...5000]
2. for each M,N pair
- factorize M using prime table from step 1
- factorize N! using prime table from step 1
- output (power of max prime in M in N!)/(power of max prime in M) if it's greater than 0 or appropriate message

Is this wrong ?
I check all I/O posted, but in all cases I got correct answer. Could anyone help me ?

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)

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Wed May 25, 2005 1:26 pm

Dominik Michniewski wrote:My algorithm is:

1. generate primes in range [2...5000]
2. for each M,N pair
- factorize M using prime table from step 1
- factorize N! using prime table from step 1
- output (power of max prime in M in N!)/(power of max prime in M) if it's greater than 0 or appropriate message

Is this wrong ?
Only consideringing the max prime factor in M is not enough. Consider cases such as:

Code: Select all

2
12 3
96 96

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

Post by Dominik Michniewski » Wed May 25, 2005 1:54 pm

Thanks.
Case 96 96 was exactly what I missed :)

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)

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan

10780 WA plz help!!!!!

Post by georgemouse » Mon Sep 12, 2005 7:04 am

I tried all the input posted in former topics and all he output is right.
BUT I still got WA!!!!!Why? :(
Can someone tell me what's wrong in my code?
Thanks!!!!!!

Code: Select all

removed after AC
Last edited by georgemouse on Tue Jan 31, 2006 4:07 pm, edited 1 time in total.

georgemouse
New poster
Posts: 13
Joined: Sun Aug 28, 2005 3:39 pm
Location: Taiwan

Post by georgemouse » Mon Sep 12, 2005 7:16 am

The way I used is to find the largest prime factor in M (the largest prime factor is K)
then find the largest power of M that divides N:
if K^a divides N!,
then I'll find the largest 'b' that k^b divides M.
At last, I'll output a/b (if it's 0 , output "Impossible to divide").

example:
if N=11,M=8=2^3
8's largest prime factor is 2
11/2->5
5/2->2
2/2->1
a=5+2+1=8
b=3
8/3=2
output 2
Last edited by georgemouse on Mon Sep 12, 2005 7:21 am, edited 1 time in total.

Post Reply

Return to “Volume 107 (10700-10799)”