## 10916 - Factstone Benchmark

Moderator: Board moderators

I feel this problem is very simple but i keep getting WA. isnt the answer same for 1960-1969,1970-1979,...

regards,

Yes, answer is the same for XXX0 - XXX9.
Test:
Code: Select all
`196021602101199919820`

Code: Select all
`32540165910128`
kp
Learning poster

Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

### 10916 - Factstone Benchmark

This is so simple problem, and I use my BigInteger class

( I think it's so fast )

But When my test year exceed 2100 then running speed

was seriously slower. ( it must calculate over 3000! )

Is there any technique for solving this problem?

// my pseudo code

while( bits can represent factorial )
{
next_number++;
factorial *= next_number;
}

return next_number;
I love Problem Solving!!!
soyoja
Experienced poster

Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea

well, biginteger method would not be so fast,
since artimethic using BigInteger is too slow to process such a big number,
thus you cannot use BIGINTEGER method!

Think about logarithms, then problem becomes more simple.

hint) log(100!) = log(1 * 2 * 3 * ... * 100) = log1 + log2 + ... + log100
Sorry For My Poor English..
wook
Learning poster

Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### Re: 10916 Time limit exceed problem

soyoja wrote:This is so simple problem, and I use my BigInteger class

( I think it's so fast )

But When my test year exceed 2100 then running speed

was seriously slower. ( it must calculate over 3000! )

Is there any technique for solving this problem?

// my pseudo code

while( bits can represent factorial )
{
next_number++;
factorial *= next_number;
}

return next_number;

problem statement wrote:Given a year 1960 ≤ y ≤ 2160

Martin Macko
A great helper

Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

isnt the answer going to be
the 21 values
for the set of years??
if yes then why am i getting WA?otherwise where am i wrong?
is there any boundary condition?
Last edited by Ankur Jaiswal on Fri May 12, 2006 10:49 pm, edited 1 time in total.
Ankur Jaiswal
New poster

Posts: 31
Joined: Sat Apr 01, 2006 6:24 am

Ankur Jaiswal wrote:isnt the answer going to be
...
for the set of years??

Do you understand that set of years is [1960,2160]?
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm

so that is what i am saying..
3 for the set of years 1960-1969
5 for 1970-1979
and so on.
isn't that rite?
Ankur Jaiswal
New poster

Posts: 31
Joined: Sat Apr 01, 2006 6:24 am

That is right. The I/O specification is too straightforward to do a mistake. Anyway you can try this
Code: Select all
`19992000200119601961216021592160`
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm

12
20
20
3
3
254016
134480
254016
Ankur Jaiswal
New poster

Posts: 31
Joined: Sat Apr 01, 2006 6:24 am

Ankur Jaiswal wrote:12
20
20
3
3
254016
134480
254016

Your output is identical mine. I think your functionality should be right, but you may need to check that your program can terminate correctly or not.
Have you ever...

Wanted to work at best companies?
Struggled with interview problems that could be solved in 15 minutes?
Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.
DD
Experienced poster

Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California