10200 - Prime Time

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

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10200 - Prime Time

Post by brianfry713 » Mon May 12, 2014 10:25 pm

Change line 96 to:
printf("%.2lf\n",cnt*100.00/(n-m+1)+1e-8);
Check input and AC output for thousands of problems on uDebug!

nasim.ruet
New poster
Posts: 10
Joined: Sat Sep 06, 2014 12:44 pm

Re: 10200 - Prime Time

Post by nasim.ruet » Sat Sep 27, 2014 9:13 pm

Please tell me the reason i got Time Limit .. please help
give me some input for this :

Code: Select all

ACCEPTED

Last edited by nasim.ruet on Tue Oct 14, 2014 10:49 pm, edited 1 time in total.

nasim.ruet
New poster
Posts: 10
Joined: Sat Sep 06, 2014 12:44 pm

Re: 10200 - Prime Time

Post by nasim.ruet » Sat Sep 27, 2014 10:17 pm

Can someone answer me why we add 1e-9 :roll: :cry:

Code: Select all

printf("%.2lf\n",(count*100.00/(b - a + 1)) + 1e-9 );

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10200 - Prime Time

Post by lighted » Mon Sep 29, 2014 2:14 pm

Don't read from file. If you don't read, post here code that you submit. Try to read this thread before posting.
Maswood Hasan Mostafi wrote:Is it possible to solve the problem
p10200 " Prime Time " with constant time?
Casimiro wrote:Hi!
Well, only if you do some sort of precalculation. Otherwise, the primality test could be done in constant time too... :wink:
Best Regards, Casimiro
Larry wrote:Precal the check for all the numbers generated, so you don't have to keep checking for each input.
Maybe if you pre-generate primes to check primality more efficiently you will avoid TLE. But i made precalculation for all values 1..10000 and saved them in array. If you do so, your simple prime-checking would be enough to get accepted. :)

We add 1e-9 because floating point numbers like float, double after calculations may have precision errors. If you learn difference how integer types and floating point types are saved in memory you will understand this more easy.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10200 - Prime Time

Post by brianfry713 » Mon Sep 29, 2014 7:27 pm

Check input and AC output for thousands of problems on uDebug!

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

Re: 10200 - Prime Time

Post by TryCatchMe » Wed Jan 07, 2015 10:45 pm

This problem was beyond frustrating. I kept getting WA and I knew my algorithm was efficient and correct. I also debugged on uDebug. Once I read the posts here and saw that BrianFry (thank you Brian!) said to add 1e-9 to your final percentage I finally got ACC. I wish the judge would just ask for the numbers in the range [a, b] since there would be no floating point errors. Had I not read this board I never would have gotten this problem accepted. Here are some tips for people:
1) add 1e-9 to your final percentage!!!
2) a prime sieve will only slow you down.
3) use uDebug!

Here is some sample I/O

Input:

Code: Select all

0 0
0 3
1 2
0 39
0 40
0 41
40 40
40 41
39 41
39 40
0 10000
9999 10000
5 10000
1 42
Output:

Code: Select all

100.00
100.00
100.00
100.00
97.56
95.24
0.00
0.00
33.33
50.00
41.49
0.00
41.46
95.24

coder.tanvir
New poster
Posts: 11
Joined: Mon Mar 09, 2015 10:30 am

Re: 10200 - Prime Time

Post by coder.tanvir » Sat Mar 21, 2015 8:32 am

after adding 1e+9, get accepted . why they dnt use special judge ? or why in ques they dnt mention that no special judge for this ques ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10200 - Prime Time

Post by brianfry713 » Tue Mar 31, 2015 12:38 am

http://uva.onlinejudge.org/index.php?op ... ategory=14
Green check regular judge, yellow special judge.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”