10200  Prime Time
Moderator: Board moderators
Re: 10200 PRIME TIME
Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re:
mf wrote:If you do preprocessing a bit cleverly, you'll be able to solve each test case in just O(1) time.
(Hint: if you know that n^2+n+41 gives A primes for interval [0,a], and B primes for [0,b], what can you tell about the interval [a+1,b]?)
why doing it my program is slower?
this code have 0.270 runtime:
Code: Select all
VI p(10001, 1);
for (int i = 0; i < 40; i++) p[i] = i + 1;
p[40] = 40;
for (int i = 41; i < 10001; i++)
p[i] = p[i  1] + prime(formula(i));
int a, b;
while (cin >> a >> b)
{
if (a == 0) cout << (double(p[b])/double(b + 1))*100 << endl;
else
{
//calculate the result
}
}
Code: Select all
VI p(10001, 1);
p[40] = 0;
for (int i = 41; i < 10001; i++)
{
p[i] = prime(formula(i));
}
int a, b;
while (cin >> a >> b)
{
double pr = 0;
for (int i = a; i <= b; i++) pr += p[i];
//calculate the result
}
Re: 10200  Prime Time
it is WA.SOME ONE HELP ME PLZ.
HERE IS MY CODE:
#include<stdio.h>
#include<math.h>
#include<memory.h>
long store[10000+12];
void is_prime(void)
{
long result,k,i,j;
for(i=0;i<=10000;i++)
{
result=i*i+i+41;
if(result%2!=0)
{
j=(long)sqrt(result);
for(k=3;k<=j;k+=2)
{
if(result%k==0) break;
}
if(k>j) store=1;
}
}
}
int main()
{
int a,b,c;
int sum,ui;
double y;
double k,g;
memset(store,0,sizeof(store));
is_prime();
while(scanf("%d %d",&a,&b)!= EOF)
{
sum=0;
if(a>b)
{
ui=a;
a=b;
b=ui;
}
for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;
}
g=ba+1;
k=sum;
y=k/g;
printf("%.2f\n",y*100);
}
return 0;
}
HERE IS MY CODE:
#include<stdio.h>
#include<math.h>
#include<memory.h>
long store[10000+12];
void is_prime(void)
{
long result,k,i,j;
for(i=0;i<=10000;i++)
{
result=i*i+i+41;
if(result%2!=0)
{
j=(long)sqrt(result);
for(k=3;k<=j;k+=2)
{
if(result%k==0) break;
}
if(k>j) store=1;
}
}
}
int main()
{
int a,b,c;
int sum,ui;
double y;
double k,g;
memset(store,0,sizeof(store));
is_prime();
while(scanf("%d %d",&a,&b)!= EOF)
{
sum=0;
if(a>b)
{
ui=a;
a=b;
b=ui;
}
for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;
}
g=ba+1;
k=sum;
y=k/g;
printf("%.2f\n",y*100);
}
return 0;
}
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10200  Prime Time
Actually i had done a silly mistake.
for double i printed "%.2Lf\n" which would be "%.0lf\n".
for double i printed "%.2Lf\n" which would be "%.0lf\n".
Code: Select all
Removed because Accepted!
Last edited by newton on Wed Sep 03, 2008 5:51 pm, edited 2 times in total.
http://www.newton.0fees.net is enough!
Re: 10200  Prime Time
newton have you tried without "eps"?
some people had WA because of this...
some people had WA because of this...
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10200  Prime Time
x140131 wrote:
is there anything wrong with my algorithm?
thanks
yes i tried but failed!newton have you tried without "eps"?
some people had WA because of this...
is there anything wrong with my algorithm?
thanks
http://www.newton.0fees.net is enough!

 Learning poster
 Posts: 53
 Joined: Sat Jul 29, 2006 7:33 am
 Location: (CSE,DU), Dhaka,Bangladesh
Re: 10200  Prime Time
Your algorithms seems to be okay.You can try in this way
just change this section
modifie to
You wouldn't need to use long double. Hope it will help you.
just change this section
Code: Select all
printf("%.2Lf\n",(cnt/(b  a + 1)*100.00)+eps);
Code: Select all
printf("%.2lf\n", ((cnt*100) / (b  a + 1)) + eps);
No venture no gain
with best regards

ishtiaq ahmed
with best regards

ishtiaq ahmed
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10200  Prime Time
Ishtiaq wrote:
however i changed but still WA
modifie toprintf("%.2Lf\n",(cnt/(b  a + 1)*100.00)+eps);
that was not the bug i think.printf("%.2lf\n", ((cnt*100) / (b  a + 1)) + eps);
however i changed but still WA
http://www.newton.0fees.net is enough!
Re: 10200  Prime Time
I've executed your program, and with
I have all wrong answers, with numbers very rare!!!!
have you tried all combinations?
....
Code: Select all
printf("%.2Lf\n",(cnt/(b  a + 1)*100.00)+eps);
have you tried all combinations?
Code: Select all
printf("%.2lf\n",((cnt*100.00)/(b  a + 1))+eps);
Code: Select all
printf("%.2f\n",((cnt*100.00)/(b  a + 1))+eps);
Code: Select all
printf("%.2lf\n",((cnt*100.00)/(b  a + 1)));
Code: Select all
printf("%.2f\n",((cnt*100.00)/(b  a + 1)));
Re: Fantastic
Joseph Kurniawan wrote:ICode: Select all
suggest to use "semihardcode".
You are a very nice man. my idea is also like so.very nice.

 New poster
 Posts: 15
 Joined: Mon Mar 31, 2008 1:20 am
 Location: Egypt
 Contact:
Re: 10200  Prime Time
Why TLE
I first generate all primes from 0 to 100010041 , and save them in array
then count the number of deprime from 0 to i from 0 to 10000
this is my code ,, any help please
thanx in advance
I first generate all primes from 0 to 100010041 , and save them in array
then count the number of deprime from 0 to i from 0 to 10000
this is my code ,, any help please
Code: Select all
deleted
Last edited by Mohamed Abd ElMonem on Tue Sep 30, 2008 12:54 am, edited 1 time in total.
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10200  Prime Time
u need not to generate primes up to sqrt of 100010041 using sieve.
Just:
Just:
Code: Select all
My Algorithm was
1. make an Boolean array of 10001
2. check isPrime( i*i + i + 41) for i> 0 to MAX
3. set array[i] true if isPrime return true;
4. scan inputs and get your answer.
http://www.newton.0fees.net is enough!
Re: 10200  Prime Time
lots of time get WA.
can anybody find the burg in my code.
i m sure enough about my algo & procedure.
tried lots of i/o.
but unsuccessful .
please brother help me.
here is my code:
can anybody find the burg in my code.
i m sure enough about my algo & procedure.
tried lots of i/o.
but unsuccessful .
please brother help me.
here is my code:
Code: Select all
#include<stdio.h>
#include<math.h>
long x,y,count,p,store[10009],temp;
double res;
bool isPrime(long x)
{
if(x == 2) return true;
if(x == 1) return false;
if(x % 2 == 0) return false;
for(int i = 3; i*i<=x; i+=2){
if(x % i == 0) return false;
}
return true;
}
int main()
{
count=0;
for(int i=0;i<=10000;i++)
{
p=(i*i)+i+41;
if(isPrime(p))
count++;
store[i]=count;
}
while(scanf("%ld%ld",&x,&y)==2)
{
if(x>y)
{
temp=x;
x=y;
y=temp;
}
if(x==0 && y==0)
{
printf("100.00\n");
continue;
}
if(x==y)
{
if(store[x]==store[x1])
{
res=((store[y]store[x])/(yx+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
if(store[x]!=store[x1])
{
res=((store[y]store[x]+1.0)/(yx+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
else
{
res=((store[y]store[x])/(yx+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
return 0;
}
 newton
 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10200  Prime Time
if else series made the code more complex.u need not to precalculate count.
1. make store boolean.
2. set store[p] = isPrime[p] for 0 to MAX
3. replace ur code to..
you need not to swap bcause a <= b.
int is enough for this problem.
why dont u practice using eps. its safe.
1. make store boolean.
2. set store[p] = isPrime[p] for 0 to MAX
3. replace ur code to..
Code: Select all
while(scanf("%d %d",&a,&b) == 2){
cnt = 0.0;
for(i = a; i<=b; i++){
if(store[i])
count = count + 1;
}
printf("%.2lf\n",(count*100.00/(b  a + 1)) + eps);
}
int is enough for this problem.
why dont u practice using eps. its safe.
http://www.newton.0fees.net is enough!

 Learning poster
 Posts: 76
 Joined: Mon Jul 21, 2008 8:50 am
 Location: SUST,SYLHET,BANGLADESH.
 Contact:
10200  prime time please help
deleted .....AC
Last edited by calicratis19 on Tue Feb 10, 2009 4:07 pm, edited 1 time in total.
Heal The World