Page 11 of 14
Re: 10200 PRIME TIME
Posted: Fri Jun 27, 2008 7:51 am
by Jan
Search the board first. Don't open a new thread if there is one already.
Re:
Posted: Sat Jul 26, 2008 2:01 am
by x140l31
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
}
}
and this have 0.180 runtime:
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
}
in both cases to "calculate the result" i do similar operations...
Re: 10200 - Prime Time
Posted: Mon Jul 28, 2008 11:34 pm
by tanmoy
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=b-a+1;
k=sum;
y=k/g;
printf("%.2f\n",y*100);
}
return 0;
}
Re: 10200 - Prime Time
Posted: Tue Sep 02, 2008 4:38 pm
by newton
Actually i had done a silly mistake.
for double i printed "%.2Lf\n" which would be "%.0lf\n".
Re: 10200 - Prime Time
Posted: Wed Sep 03, 2008 1:12 am
by x140l31
newton have you tried without "eps"?
some people had WA because of this...
Re: 10200 - Prime Time
Posted: Wed Sep 03, 2008 5:15 am
by newton
x140131 wrote:
newton have you tried without "eps"?
some people had WA because of this...
yes i tried but failed!
is there anything wrong with my algorithm?
thanks
Re: 10200 - Prime Time
Posted: Wed Sep 03, 2008 2:52 pm
by ishtiaq ahmed
Your algorithms seems to be okay.You can try in this way
just change this section
Code: Select all
printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);
modifie to
Code: Select all
printf("%.2lf\n", ((cnt*100) / (b - a + 1)) + eps);
You wouldn't need to use long double. Hope it will help you.
Re: 10200 - Prime Time
Posted: Wed Sep 03, 2008 3:02 pm
by newton
Ishtiaq wrote:
printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);
modifie to
printf("%.2lf\n", ((cnt*100) / (b - a + 1)) + eps);
that was not the bug i think.
however i changed but still WA
Re: 10200 - Prime Time
Posted: Wed Sep 03, 2008 6:19 pm
by x140l31
I've executed your program, and with
Code: Select all
printf("%.2Lf\n",(cnt/(b - a + 1)*100.00)+eps);
I have all wrong answers, with numbers very rare!!!!
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
Posted: Sun Sep 07, 2008 10:18 pm
by debugger
Re: 10200 - Prime Time
Posted: Fri Sep 26, 2008 4:09 am
by Mohamed Abd El-Monem
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
Re: 10200 - Prime Time
Posted: Fri Sep 26, 2008 3:05 pm
by newton
u need not to generate primes up to sqrt of 100010041 using sieve.
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.
Re: 10200 - Prime Time
Posted: Sat Sep 27, 2008 10:48 am
by sreejond
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:
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[x-1])
{
res=((store[y]-store[x])/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
if(store[x]!=store[x-1])
{
res=((store[y]-store[x]+1.0)/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
else
{
res=((store[y]-store[x])/(y-x+1.0))*100.00;
printf("%.2lf\n",res);
continue;
}
}
return 0;
}
Re: 10200 - Prime Time
Posted: Sat Sep 27, 2008 6:33 pm
by newton
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..
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);
}
you need not to swap bcause a <= b.
int is enough for this problem.
why dont u practice using eps. its safe.
10200 - prime time please help
Posted: Thu Oct 09, 2008 10:21 pm
by calicratis19
deleted .....AC
