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

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

...

Post by Fuad Hassan EWU » Thu Sep 27, 2007 4:52 pm

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

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

Re: ...

Post by Jan » Thu Sep 27, 2007 5:38 pm

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?
Yes you are right.
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.
You can post your new code. Yes, you should have given MLE. But I dont know why WA was given.
Ami ekhono shopno dekhi...
HomePage

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

plz help

Post by Fuad Hassan EWU » Thu Sep 27, 2007 8:51 pm

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

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

Post by Jan » Fri Sep 28, 2007 8:46 am

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

..

Post by Fuad Hassan EWU » Sat Sep 29, 2007 9:23 pm

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. :( :evil: :( :evil: :( plz help me. thank you.
Eagle er moto daana meley urbo

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

Post by Jan » Sun Sep 30, 2007 9:16 am

Try using

Code: Select all

printf("%.2lf\n",result+1e-7);
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

...

Post by Fuad Hassan EWU » Sun Sep 30, 2007 12:04 pm

Yes jan vai Finally it is accepted. :D thank you very much. :D 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.
Eagle er moto daana meley urbo

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

Post by Jan » Sun Sep 30, 2007 12:11 pm

Check the link below..

http://online-judge.uva.es/board/viewto ... c&start=27
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

User avatar
Fuad Hassan EWU
New poster
Posts: 38
Joined: Tue Jul 17, 2007 3:21 pm
Location: East West University

..

Post by Fuad Hassan EWU » Sun Sep 30, 2007 2:33 pm

thanks jan vai, now i am clear.
Eagle er moto daana meley urbo

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

10200 WA please help

Post by alamgir kabir » Fri Oct 26, 2007 6:08 pm

I got AC at last.

Code: Select all

//code removed
Thanks sapnil.
Last edited by alamgir kabir on Sun Oct 28, 2007 1:42 pm, edited 2 times in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Fri Oct 26, 2007 6:37 pm

Try this cases

Code: Select all

1 10000
1 1
2 2
1 2
output:
41.48
100.00
100.00
100.00
Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Tue Feb 26, 2008 12:10 pm

thanks jan vai. at last i got AC.
i just forgot a small precision error.
''I want to be most laziest person in the world''

ChiperOrtizII
New poster
Posts: 2
Joined: Mon Apr 14, 2008 7:44 pm

Post by ChiperOrtizII » Mon Apr 14, 2008 7:52 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

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.

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

Re: 10200 - Prime Time

Post by Jan » Mon Apr 14, 2008 11:03 pm

Read previous threads. For each query you don't have to run a loop like..

Code: Select all

for I:= A To B Do
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.
Ami ekhono shopno dekhi...
HomePage

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

10200 PRIME TIME

Post by tanmoy » Thu Jun 26, 2008 3:01 am

SOMEBODY PLEASE HELP ME :(
IT IS WA :evil:
WHY ?
HERE IS MY CODE .IT PASSES ALL THE INPUT VALUES WHICH I CAN FIND.
PLEASE HELP ME :cry:

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

Post Reply

Return to “Volume 102 (10200-10299)”