## 10916 - Factstone Benchmark

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

Moderator: Board moderators

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

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

``````1960
2160
2101
1999
1982
0
``````

Code: Select all

``````3
254016
5910
12
8
``````

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

### 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?

Plz tell me about hint.

// my pseudo code

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

return next_number;
I love Problem Solving!!!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
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..

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### 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?

Plz tell me about hint.

// 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

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:
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.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Ankur Jaiswal wrote:isnt the answer going to be
...
for the set of years??
Do you understand that set of years is [1960,2160]?

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:
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?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
That is right. The I/O specification is too straightforward to do a mistake. Anyway you can try this

Code: Select all

``````1999
2000
2001
1960
1961
2160
2159
2160``````

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

12
20
20
3
3
254016
134480
254016

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

### Re: my answers

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.

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm