10200 - Prime Time
Moderator: Board moderators
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
...
that means jan vai you are telling that i will have to generate prime upto sqrt(100010041) and collect hose primes and then check whether 100010041 is prime or not in terms of worst case by checking whether 100010041 is divisible by any prime number upto sqrt(100010041), am i right? bt jan vai why my code is giving WA. i use more memory then it should have been given me memory limit exceed. plz explain this. thank you.
Eagle er moto daana meley urbo
Re: ...
Yes you are right.Fuad Hassan EWU wrote:that means jan vai you are telling that i will have to generate prime upto sqrt(100010041) and collect hose primes and then check whether 100010041 is prime or not in terms of worst case by checking whether 100010041 is divisible by any prime number upto sqrt(100010041), am i right?
You can post your new code. Yes, you should have given MLE. But I dont know why WA was given.Fuad Hassan EWU wrote: bt jan vai why my code is giving WA. i use more memory then it should have been given me memory limit exceed. plz explain this. thank you.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
plz help
jan vai i chage the code as bellow, now i am again having WA.
Code: Select all
AC
Last edited by Fuad Hassan EWU on Sun Sep 30, 2007 12:05 pm, edited 3 times in total.
Eagle er moto daana meley urbo
Two things you should remember...
1. sqrt() is a slow function. So, you can store the value of sqrt(f) in a varibale, cause then you dont have to use sqrt(f) all the time.
2. Precalculate all the numbers. Suppose A[X] will store how many primes you have found using n = 0 to X. So, before taking any input, build the array A. Then each query can be answered in just O(1) time.
Hope these help.
1. sqrt() is a slow function. So, you can store the value of sqrt(f) in a varibale, cause then you dont have to use sqrt(f) all the time.
2. Precalculate all the numbers. Suppose A[X] will store how many primes you have found using n = 0 to X. So, before taking any input, build the array A. Then each query can be answered in just O(1) time.
Hope these help.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
..
jan vai i edited the code above, now i am getting WA. i am not finding the way. how many days i will have to hang around with this simple problem.
plz help me. thank you.
![:(](./images/smilies/icon_frown.gif)
![:evil:](./images/smilies/icon_evil.gif)
![:(](./images/smilies/icon_frown.gif)
![:evil:](./images/smilies/icon_evil.gif)
![:(](./images/smilies/icon_frown.gif)
Eagle er moto daana meley urbo
Try using
Hope it helps.
Code: Select all
printf("%.2lf\n",result+1e-7);
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
...
Yes jan vai Finally it is accepted.
thank you very much.
but if u plz explain me why i had to use result+1e-7, i mean i want to know the reason behind it. thank you again.
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
Eagle er moto daana meley urbo
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 38
- Joined: Tue Jul 17, 2007 3:21 pm
- Location: East West University
-
- New poster
- Posts: 37
- Joined: Wed Oct 03, 2007 10:42 am
10200 WA please help
I got AC at last.
Thanks sapnil.
Code: Select all
//code removed
Last edited by alamgir kabir on Sun Oct 28, 2007 1:42 pm, edited 2 times in total.
Try this cases
Thanks
Keep posting
Sapnil
Code: Select all
1 10000
1 1
2 2
1 2
output:
41.48
100.00
100.00
100.00
Keep posting
Sapnil
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@
-
- New poster
- Posts: 2
- Joined: Mon Apr 14, 2008 7:44 pm
Hi This Is My First Entry At The Forum I Dont Know If I Did It Wrong.... Can SomeBody Give Some Tricks About 10200 Prime Time I´m Getting TL IN Pascal.. Pascal Was My First Languague To Program But I dont use It Often Later I Use Java Instead
Please Help Cristian Ortiz Venezuela
Please Help Cristian Ortiz Venezuela
Code: Select all
{$N+}
Const
LimiA = 10005;
LimiB = 1230;
Var
Vec : Array[1..LimiA] Of boolean;
Primes : Array[1..LimiB] Of Integer;
PosA,a,b : Integer;
Archivo : Text;
Sol : double;
I,SolA : LongInt;
Opc : LongInt;
Sw : boolean;
Car : Char;
Procedure Sieve(L:Integer;U:Integer);
Var
I,J:Integer;
AuxCon : Integer;
Begin
For I:= L To U Do
If (Not Vec[i]) Then
Begin
AuxCon:= (I+I);
While(AuxCon <= U) Do
Begin
Vec[AuxCon] := True;
AuxCon := AuxCon + i;
End;
End;
End;
Procedure Load;
Var
I,Pos : Integer;
Begin
Pos := 1;
For I:= 2 To LimiA Do
Begin
if (Not Vec[i]) Then
Begin
Primes[Pos]:= i;
Pos:= Pos+1;
End;
End;
End;
Function Solucion(L:Integer; U: Integer) : Integer;
Var
I,Aux,Sol: Integer;
Begin
PosA:= 0;
Sol:= 0;
For I:= L To U Do
Begin
Aux := (i*i)+i+41;
PosA:= PosA+1;
if (Not Vec[Aux]) Then Sol:= Sol+1;
End;
Solucion:= Sol;
End;
Function IsPrime(Num:LongInt) : Boolean;
Var
I,x : Integer;
Sw : Boolean;
Begin
Sw:= true;
For I:= 1 To 1229 Do
Begin
if (Num Mod Primes[i] = 0) Then
Begin
Sw:= false;
break;
End;
End;
IsPrime:= Sw;
End;
Begin
Sieve(2,LimiA);
Load;
while (Not Eof) Do
Begin
Readln(a,b);
If ((b*b)+b+41 <= LimiA) Then
Sol:= (Solucion(a,b)*100)/PosA
Else
Begin
SolA:= 0; PosA := 0;
for I:= A To B Do
Begin
Opc := I;
Opc := I*I;
Opc := Opc + i+41;
Sw:= IsPrime(Opc);
PosA:= PosA+1;
if (Sw) Then SolA:= SolA+1;
End;
Sol := (SolA*100)/PosA;
End;
Writeln(Sol:0:2);
End;
End.
Re: 10200 - Prime Time
Read previous threads. For each query you don't have to run a loop like..
Before taking inputs make an array say M[]. M[x] will store the number of primes (using the formula) from 0 to x. Then you can answer each query easily.
Code: Select all
for I:= A To B Do
Ami ekhono shopno dekhi...
HomePage
HomePage
10200 PRIME TIME
SOMEBODY PLEASE HELP ME
IT IS WA
WHY ?
HERE IS MY CODE .IT PASSES ALL THE INPUT VALUES WHICH I CAN FIND.
PLEASE HELP ME
#include<stdio.h>
#include<math.h>
int store[10002+5];
int is_prime(int a)
{
int c;
if (a==1) return 0;
if (a==2) return 1;
if (a%2==0)return 0;
c= int(sqrt(a));
int x;
x=int(c);
for(x=3;x<=c;x+=2)
if(a%x==0)return 0;
return 1;
}
int is_prime(int a);
int main()
{
int a,b,c;
int l;
int sum;
float y;
float k;
for(a=0;a<=10002;a++)
{
l=int(pow(a,2));
if(is_prime(l+a+41)==1)store[a]=1;
else store[a]=0;
}
while(scanf("%d %d",&a,&b)==2)
{ sum=0;
for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;
}
int g=b-a+1;
k=float(sum*100.00);
y=float(k/g);
printf("%2.2f\n",y);
}
return 0;
}
![:(](./images/smilies/icon_frown.gif)
IT IS WA
![:evil:](./images/smilies/icon_evil.gif)
WHY ?
HERE IS MY CODE .IT PASSES ALL THE INPUT VALUES WHICH I CAN FIND.
PLEASE HELP ME
![:cry:](./images/smilies/icon_cry.gif)
#include<stdio.h>
#include<math.h>
int store[10002+5];
int is_prime(int a)
{
int c;
if (a==1) return 0;
if (a==2) return 1;
if (a%2==0)return 0;
c= int(sqrt(a));
int x;
x=int(c);
for(x=3;x<=c;x+=2)
if(a%x==0)return 0;
return 1;
}
int is_prime(int a);
int main()
{
int a,b,c;
int l;
int sum;
float y;
float k;
for(a=0;a<=10002;a++)
{
l=int(pow(a,2));
if(is_prime(l+a+41)==1)store[a]=1;
else store[a]=0;
}
while(scanf("%d %d",&a,&b)==2)
{ sum=0;
for(c=a;c<=b;c++)
{
if(store[c]==1)sum++;
}
int g=b-a+1;
k=float(sum*100.00);
y=float(k/g);
printf("%2.2f\n",y);
}
return 0;
}