10200 - Prime Time

[brianfry713]

Change line 96 to:
printf("%.2lf\n",cnt*100.00/(n-m+1)+1e-8);

[nasim.ruet]

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

Code: Select all

ACCEPTED

[nasim.ruet]

Can someone answer me why we add 1e-9

Code: Select all

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

[lighted]

Don't read from file. If you don't read, post here code that you submit. Try to read this thread before posting.

Is it possible to solve the problem
p10200 " Prime Time " with constant time?

Hi!
Well, only if you do some sort of precalculation. Otherwise, the primality test could be done in constant time too...
Best Regards, Casimiro

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.

[brianfry713]

http://floating-point-gui.de/

[TryCatchMe]

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]

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]

http://uva.onlinejudge.org/index.php?op ... ategory=14
Green check regular judge, yellow special judge.