10533 - Digit Primes

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10533

Post by Eduard » Sat Nov 29, 2003 1:45 pm

help please my program works fast and correct on my computer but gives WA. help pleas.[pascal]program acm10533;
var i,j,a,b,number,p,k,i1:longint;
c:array[0..1000000] of longint;
l:boolean;
procedure parz(n:longint;var h:boolean);
label 1;
var i:integer;
begin
h:=true;
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then begin h:=false;goto 1;end;
1:
end;
begin
read(number);
c[0]:=0;
for i:=1 to 1000000 do
begin
k:=0;
i1:=i;
parz(i,l);
if l=true then
begin
repeat
k:=k+(i mod 10);
i:=i div 10;
until i=0;
i:=i1;
parz(k,l);
if l=true then c:=c[i-1]+1 else c:=c[i-1];
end else c:=c[i-1];
end;
for p:=1 to number do
begin
read(a,b);
writeln(c-c[a]);
end;
end.
[/pascal]
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Critical Inputs

Post by sohel » Sat Dec 27, 2003 7:19 am

Hi Eduard,
I am not an expert in interpreting PASCAL code, but here is some critical inputs.

What is your output for the following cases:

10
5 8
1 999999
11 25
3 3
5 6
6 7
1 100
9 10
200 300
12 13

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Dec 30, 2003 12:49 pm

My answers are

1
30123
1
1
0
1
14
0
8
0
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

osan
New poster
Posts: 47
Joined: Tue Jul 29, 2003 12:03 pm
Location: Bangladesh,Dhaka.
Contact:

REAL OUTPUT FOR THOSE INPUT

Post by osan » Fri Jan 09, 2004 2:35 pm

INPUT
11
5 8
1 999999
11 25
3 3
5 6
6 7
1 100
9 10
200 300
12 13
1 10

OUTPUT
2
56
2
1
1
1
14
0
8
0
4
this time WA
what next...............?

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

TLE :(

Post by pavelph » Mon Jan 26, 2004 9:08 pm

Hi! I have TLE on this problem, but I don't know how I can make my program faster.
I have algo that:
1) get_primes_numbers (Eratosphean)
2) get_digit_primes_numbers
It makes

Code: Select all

d: array [1 .. 1000000] of boolean
and d=true if i - digit prime. And this two procedures works <1 sec. !!!
It means that very slow work procedure that count how many 'true' values in array from t1 to t2. Help me please, how I can optimise this procedure:
[pascal] readln(n);
for i:=1 to n do begin
readln(n1, n2);
counter:=0;
if not odd(n1) then inc(n1);
while n1<=n2 do begin
if d[n1] then inc(counter);
inc(n1, 2);
end;
writeln(counter);
end;
[/pascal]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Jan 27, 2004 12:11 am

Have you ever considered a second lookup table that consists of the number of digit primes less than or equal to the index?

No point in repeating boolean checks for 1...999999, then 1...999998, then 1...999997, etc.

Just do it once, and extrapolate the answer given the range.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Tue Jan 27, 2004 8:02 pm

Oh, yes, of course :) It's really very easy.
Thank you very much, now I have got AC on 10533 in 5 sec. :wink:

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Tue Feb 17, 2004 8:12 am

First time, I tried to find amount of digit prime to use binary search...

( Using index of digit prime stored array )

But there are some problems...

( Binary search has some problem when an index value has no

digit prime, and so on... )

So I use 1,000,000 size integer array

and accumulate all digit prime, and range value to calculate

accumulated array.

P.S ) When I use Visual C++, I can only set 250,000 size integer

array. So I use gcc, and I can declare one million size int array.

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal

Post by playerX » Wed Feb 18, 2004 12:14 am

i'm having wa... probably a small mistake, i'll look at it more attentively
be cool...

Kamanashish
New poster
Posts: 10
Joined: Wed Dec 17, 2003 3:12 pm
Location: Dhaka
Contact:

10533 - Digit Primes

Post by Kamanashish » Mon Jun 14, 2004 2:57 pm

I can not understand what is the wrong with it.Have there any critical input?


//Cutted
Last edited by Kamanashish on Tue Jun 15, 2004 4:14 pm, edited 1 time in total.
Work hard.

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Post by Rajib » Tue Jun 15, 2004 8:59 am

if(a[l]=='1')c++;
Do you think this portion will work correct... :o

13 is a prime number but not a digit prime. But in that protion you increase c by one (c++) if lower bound (l) is prime only. You must test whether (l) is a digit prime... :lol:

Test these:

Input:
3
3 5
13 13
11 13
Output:
2
0
1
Goodluck...
All the part of your code seem correct. Cut the code if you get AC. :roll:

Kamanashish
New poster
Posts: 10
Joined: Wed Dec 17, 2003 3:12 pm
Location: Dhaka
Contact:

Post by Kamanashish » Tue Jun 15, 2004 4:11 pm

Thanks Rajib. At last i have got AC.
Work hard.

jahangirk
New poster
Posts: 5
Joined: Sat Jun 26, 2004 11:15 pm

10533. Digit prime . Why TLE .. Somebody help me plzzzzz

Post by jahangirk » Sun Jul 04, 2004 1:53 pm

i m getting time limit exceed . plz help me i dont know y



[cpp]




#include<stdio.h>



bool checkprime(int num)
{
int flag=0;

if(num==2)
{
return true;
}
else
{
int count=2;
while(count<=(num/2)+1)
{
flag = 0;
if((num%count)==0)
{
flag=1;
break;
}
count=count+1;
}
if(flag!=1)
{
return true;
}
return false;
}


}




int main()
{
bool v;
int lim;
int i;

scanf("%d",&lim);

int upper,lower;

for(int k=0;k<lim;k++)
{
int total=0;

scanf("%d",&lower);
scanf("%d",&upper);




for(i=lower;i<upper;i++)
{



v=checkprime(i);

if(v==true)
{

int sum=0;

if(i>10)
{
int n=i;
int rem;


while(n>=10)
{
rem=n%10;
n=n/10;

sum=sum+rem;
}
sum=sum+n;

if(checkprime(sum))
{
total=total+1;
}


}

}
else
{
if(checkprime(i))
{
total=total+1;
}
}




}
printf("%d",total);
printf("\n");
}
return 0;
}


[/cpp]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Jul 04, 2004 3:42 pm

Your prime testing method is highly inefficient. There are posts that has efficient method to test prime.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Jul 17, 2004 3:30 pm

Hi,
Besides the efficiency of ur prime testing function, there are other things u should look at.
As the number of test cases is 500000, u must use dynamic programming here.
And u better use the sieve method to generate all the primes.

Post Reply

Return to “Volume 105 (10500-10599)”