10856 - Recover Factorial

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

Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

10856 - Recover Factorial

Post by BiK » Sat May 28, 2005 4:08 pm

How is this problem solved? It appears everybody but me solved it :(

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

Post by zhang » Sat May 28, 2005 4:27 pm

:cry: I want to know,also. I can't solve this problem in 2s.
Tell me and Bik how to solve the problem.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun May 29, 2005 6:45 am

Hi

I have solve this problem by this way
- First i have stored some prime number
- Then i have stored number of factor's in a single number by using DP.
- Then binary search

Thanks :)
MAP

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon May 30, 2005 2:23 pm

mohiul alam prince wrote:Hi

I have solve this problem by this way
- First i have stored some prime number
- Then i have stored number of factor's in a single number by using DP.
- Then binary search
MAP
Sorry, I got WA all the time.
Could you give me some tricky input/output?
Thx

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Mon May 30, 2005 2:50 pm

Maybe this, in the problem statement is:
A negative integer marks is the end of input, not -1. :wink: I have 2 WAs becouse of that...

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon May 30, 2005 3:22 pm

Monsoon wrote:Maybe this, in the problem statement is:
A negative integer marks is the end of input, not -1. :wink: I have 2 WAs becouse of that...
I have noticed the point.
When I input 0, it is impossible or 1! ?

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Mon May 30, 2005 3:26 pm

neither of them, i output 0 (0!=1) and it is the smallest number

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Tue May 31, 2005 8:36 am

Hi
Try this Input

Input

Code: Select all

0
1
10000001
-200
Output

Code: Select all

Case 1: 0!
Case 2: 2!
Case 3: 2703663!
I think this is the most tricky Input for this problem.

Thanks
MAP

schindlersp
New poster
Posts: 28
Joined: Tue Aug 03, 2004 8:11 pm
Contact:

10856

Post by schindlersp » Thu Jul 07, 2005 8:29 pm

0! = 1

am i right? i think so is not possible this case.

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Wed Jul 27, 2005 5:13 am

mohiul alam prince wrote:Hi

I have solve this problem by this way
- First i have stored some prime number
- Then i have stored number of factor's in a single number by using DP.
- Then binary search

Thanks :)
MAP
I tried to store prime upto 2703663 and it take 1.6 MB.
Can you write details?

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Jul 27, 2005 12:15 pm

Hi ibrahim

suppose you have a list of prime number
- prime[] = {2,3,5,7,11,13,17,19,23,29,............................}
- and my concept is if a number is divisible by a prime number then it is suffice for find out total number of prime factor.
exp - if we have a number 12
then we have to check which prime number is divisible then 2 will be come and
then ans will be Table = Table[i / prime[j]] + Table[prime[j]];
here i = 12
prime[j] = 2
then Table[12] = Table[12/2] + Table[2]
then we can easily find out Table[12] = 3:-?
and it will be continue up to 2703665

- then binary search

thanks :)
MAP

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Sat Aug 20, 2005 11:39 am

Table = Table[i / prime[j]] + Table[prime[j]];

what does this table contain at last...
how does it help....
plz, give me explanations and some starting values in the generated table
Thanks !

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Thu Apr 13, 2006 4:35 am

I don't understand too
12 has another prime factor is 3 then table[12] = table[4] + table[3] + table[6] + table[2] ?

some little more details please?

a123123123888
New poster
Posts: 7
Joined: Fri Mar 31, 2006 1:22 pm

Post by a123123123888 » Tue Jul 04, 2006 10:51 am

The table at last is like this:

Code: Select all

Table[0]=0
Table[1]=0
Table[2]=1
Table[3]=1
Table[4]=2
Table[5]=1
Table[6]=2
Table[7]=1
Table[8]=3
...
This means the number's "factors" --> I don't know whether this word or not

Example
8 = 2 * 2 * 2
So Table[8]=3

to FAQ:

Code: Select all

Table[4]+Table[3]+Table[6]+Table[2]
means

Code: Select all

Table [ 4 * 3 * 6 * 2 ] = Table[144]
and obviously not equal to Table [12].

By the way, it's not necessary to calculate prime numbers.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Sun Jul 30, 2006 6:35 am

Can anybody post some testcases? My code seems to be correct but still WA.
now I got it, I didn't print the '.' !!!

Post Reply

Return to “Volume 108 (10800-10899)”