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

Post Reply
Dickon
New poster
Posts: 4
Joined: Thu Jun 15, 2006 4:10 am

Post by Dickon »

thank you very much , i will try it.

Dickon
New poster
Posts: 4
Joined: Thu Jun 15, 2006 4:10 am

Re: 10200(time limited~help)

Post by Dickon »

thank for your suggestion,i get AC.

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita »

TLE :-? :-? :-? why????????????

Code: Select all

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
bool prime(long long int j)
{    bool fl=true;
     if(j==0 && j==1)
     return true;
     else
     {
     for (long long int t=2;t<=sqrt(j);t++)
     {
     if(j%t==0)
     {        
        fl=false;
              }
              }
     if(fl==false)
     return false;
     if(fl==true)
     return true;
     }
     }
int main()
{
    int a,b,k=2;
    int v[10001];
    v[0]=0;v[1]=1;
    for (int h=3;h<=10001;h=h+2)
    {
        if(prime(h)==true)
        {
         v[k]=h;
         k++;
         }
         }
    while (cin>>a>>b)
    {
           bool flag1=false,flag2;
           int c2=0;        
           
              for (int i=a;i<=b;i++){flag2=true;   
               long long int m=i*i+i+41;
               
               for(int q=2;q<k && v[q]<sqrt(m);q++)
               {if(m%v[q]==0)
                flag2=false;
               }
               if (flag2==true && i!=40)
               c2+=1;
               
               }
               double pr;
               pr=(double(c2)/double(b-a+1))*100.0;
               cout<<setiosflags(ios::fixed)<<setprecision(2)<<pr<<endl;
               }
               return 0;
               }
help me out.......plz....[/b]
win

Tahasin
New poster
Posts: 6
Joined: Tue Jun 27, 2006 7:19 am

10200 WA

Post by Tahasin »

#include<stdio.h>
#include<math.h>
main()
{
int a,b,c,k[10000],i,j,t,prime,count=0,m,n,counter;float s,p,q;
for(i=0;i<=10000;i++)
{
prime=1;
a=i*i+i+41;b=sqrt(a);
for(j=2;j<=b;j++)if(a%j==0)prime=0;
if(prime){k[count]=i;count++;printf("%d,",i);}
}
printf("\n\n%d",count);
/*while((scanf("%d%d",&m,&n))==2)
{
counter=0;
for(i=m;i<=n;i++)
{
for(j=0;j<count;j++){if(i==k[j]){counter++;break;}}
}s=n-m+1;p=counter;q=(counter/s)*100;
printf("%.2f\n",q);
}*/
return 0;
}

rushafi
New poster
Posts: 2
Joined: Wed Sep 13, 2006 7:25 pm
Location: Dhaka, Bangladesh.

whats the prob?

Post by rushafi »

i am getting WA over and over again. I've tested some of Minilek's cases and found some fault. Actually the answer is too near. I am unable to find the problem so far.

A little help will be very much appriciated.

here is 3 test cases 4 xample:

3957 8978
8138 9707
843 8651


my ans:

38.53
37.07
40.40


minilek's ans:

38.51
37.01
40.39


and my code:

#include<stdio.h>
#include<math.h>

int count[10005];

int main(){
int flag,total,temp,a,b;
long prime,z;
double ans;
count[0]=1;
for (int i=1;i<10005;i++){
prime=i*i+i+41;
flag=1;
if (prime%2==0) flag=0;
else {
z=ceil(sqrt(prime));
for(int c=3;c<=z;c+=2){
if (prime%c==0){
flag=0;
break;
}
if (flag==0) break;
}
}
count=count[i-1]+flag;
}
while(scanf("%d %d",&a,&b)==2){
if ((count==count[a]) && (count[a]==count[a-1])) temp=0;
else{
total=b-a+1;
temp=count-count[a]+1;
}
ans=(temp*100.)/total;
printf("%.3lf\n",ans);
}
return 0;
}

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: whats the prob?

Post by little joey »

Please use code tags! This is much better for the reader of your message:

Code: Select all

#include<stdio.h>
#include<math.h>

int count[10005];

int main(){
	int flag,total,temp,a,b;
	long prime,z;
	double ans;
	count[0]=1;
	for (int i=1;i<10005;i++){
		prime=i*i+i+41;
		flag=1;
		if (prime%2==0) flag=0;
		else {
			z=ceil(sqrt(prime));
			for(int c=3;c<=z;c+=2){
				if (prime%c==0){
					flag=0;
					break;
				}
			if (flag==0) break;
			}
		}
		count[i]=count[i-1]+flag;
	}
	while(scanf("%d %d",&a,&b)==2){
		if ((count[b]==count[a]) && (count[a]==count[a-1])) temp=0;
		else{
			total=b-a+1;
			temp=count[b]-count[a]+1;
		}		
		ans=(temp*100.)/total;
		printf("%.3lf\n",ans);
	}
	return 0;
}

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

Does the problem be rejudged?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Yes, it did been.
The judge now only accepts the correct answer.

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

Post by abhi »

i am sure that my code is right . but i get WA plz help me out ...

Code: Select all

# include <stdio.h>

int prime[10010];

void genprime()
{
    int i,j;
    
    for(i=0;i<=10010;i++)   prime[i]=i;
    
    prime[0]=prime[1]=0;
     
    for(j=4;j<=10010;j+=2)  prime[j]=0;
    
    for(i=3;i*i<=10010;i+=2)
        if(prime[i])
            for(j=i*i;j<=10010;j+=i)
                prime[j]=0;
}

int isprime(int n)
{
   int i,j;
   
   
   if(n<2 || n%2 == 0 || n%5 == 0)  return 0;
   
   for(i=0;prime[i]*prime[i]<=n;i++)
    if(prime[i])
    if(n%prime[i] == 0)
        return 0;
        
    return 1;
}
        
int main()
{
    int  i,j,m,n;
    double count;
    int flag[10005]={0};
    
    genprime();
    
       for(i=0;i<=10000;i++){
            if(isprime(i*i+i+41))
                flag[i]=1; 
            }
    while(scanf("%d %d",&m,&n) == 2)
    {
        count = 0.0;
     
        
        for(i=m;i<=n;i++){
            if(flag[i])
                count++;
                                          
        }
                
        printf("%.2lf\n",(count/(n-m+1))*100);
    }
return 0;
}

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

My previous code is accept.
When I submit it again,it got WA.
I don't know what change in the problem.
I test many test data then still got WA.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Try adding EPS to the result before printing. It fixed my solution.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA »

Darko wrote:Try adding EPS to the result before printing. It fixed my solution.
Thank you!
I set EPS to 10^-9 and got AC!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 »

AC
Self judging is the best judging!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

little joey wrote:Yes, it did been.
The judge now only accepts the correct answer.
Also, it now rejects correct answers if you round them with cin.

I believe any problem that asks to ouput 'up to some precision' should specify how to round or have a special correction program :evil:

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Only if the answer is the result of floating point calculations. In this problem you can calculate the correct answer using integers only, so there is no need for a special corrector.

Post Reply

Return to “Volume 102 (10200-10299)”