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

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

Re: 10916 Please help!!!!!!!!!!!

Post by kp » Sun Oct 02, 2005 12:21 am

pradeepm wrote:Hi!!
I feel this problem is very simple but i keep getting WA. isnt the answer same for 1960-1969,1970-1979,...
please give me some test cases. please help me..

regards,
Pradeep
Yes, answer is the same for XXX0 - XXX9.
Test:

Code: Select all

1960
2160
2101
1999
1982
0
Answer:

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

Post by soyoja » Mon Nov 07, 2005 9:34 am

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

Post by wook » Mon Nov 07, 2005 9:43 am

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.. :)

User avatar
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

Post by Martin Macko » Sat Dec 10, 2005 9:39 pm

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;
Think about this sentence in the problem statement:
problem statement wrote:Given a year 1960 ≤ y ≤ 2160

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

Post by Ankur Jaiswal » Wed May 10, 2006 1:12 am

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
Location: Bangladesh
Contact:

Post by mamun » Wed May 10, 2006 6:49 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]?

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

Post by Ankur Jaiswal » Wed May 10, 2006 11:18 am

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
Location: Bangladesh
Contact:

Post by mamun » Wed May 10, 2006 11:44 am

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:

my answers

Post by Ankur Jaiswal » Wed May 10, 2006 11:47 am

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

Post by DD » Tue Mar 15, 2011 7:48 pm

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.

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

Re: 10916 - Factstone Benchmark

Post by uDebug » Tue Feb 25, 2014 2:23 pm

Replying to follow this thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 109 (10900-10999)”