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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10200 PRIME TIME

Post by Jan » Fri Jun 27, 2008 7:51 am

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re:

Post by x140l31 » Sat Jul 26, 2008 2:01 am

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

tanmoy
New poster
Posts: 18
Joined: Wed Jun 25, 2008 2:25 pm

Re: 10200 - Prime Time

Post by tanmoy » Mon Jul 28, 2008 11:34 pm

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;
}

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10200 - Prime Time

Post by newton » Tue Sep 02, 2008 4:38 pm

Actually i had done a silly mistake.
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.

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 10200 - Prime Time

Post by x140l31 » Wed Sep 03, 2008 1:12 am

newton have you tried without "eps"?

some people had WA because of this...

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10200 - Prime Time

Post by newton » Wed Sep 03, 2008 5:15 am

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

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

Re: 10200 - Prime Time

Post by ishtiaq ahmed » Wed Sep 03, 2008 2:52 pm

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.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10200 - Prime Time

Post by newton » Wed Sep 03, 2008 3:02 pm

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

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 10200 - Prime Time

Post by x140l31 » Wed Sep 03, 2008 6:19 pm

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

debugger
New poster
Posts: 8
Joined: Tue Jul 29, 2008 6:24 pm

Re: Fantastic

Post by debugger » Sun Sep 07, 2008 10:18 pm

Joseph Kurniawan wrote:I

Code: Select all

suggest to use "semi-hardcode".

You are a very nice man. my idea is also like so.very nice. :lol: :lol: :lol: :lol: :lol: :lol:

Mohamed Abd El-Monem
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

Re: 10200 - Prime Time

Post by Mohamed Abd El-Monem » Fri Sep 26, 2008 4:09 am

Why TLE :oops: :oops:

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 
thanx in advance
Last edited by Mohamed Abd El-Monem on Tue Sep 30, 2008 12:54 am, edited 1 time in total.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10200 - Prime Time

Post by newton » Fri Sep 26, 2008 3:05 pm

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.

User avatar
sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

Re: 10200 - Prime Time

Post by sreejond » Sat Sep 27, 2008 10:48 am

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;
}

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10200 - Prime Time

Post by newton » Sat Sep 27, 2008 6:33 pm

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.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

10200 - prime time please help

Post by calicratis19 » Thu Oct 09, 2008 10:21 pm

deleted .....AC
Last edited by calicratis19 on Tue Feb 10, 2009 4:07 pm, edited 1 time in total.
Heal The World

Post Reply

Return to “Volume 102 (10200-10299)”