Page 2 of 8
Posted: 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;
c:array[0..1000000] of longint;
procedure parz(n:longint;var h:boolean);
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then begin h:=false;goto 1;end;
for i:=1 to 1000000 do
if l=true then
k:=k+(i mod 10);
i:=i div 10;
if l=true then c:=c[i-1]+1 else c:=c[i-1];
end else c:=c[i-1];
for p:=1 to number do
Posted: Sat Dec 27, 2003 7:19 am
I am not an expert in interpreting PASCAL code, but here is some critical inputs.
What is your output for the following cases:
Posted: Tue Dec 30, 2003 12:49 pm
My answers are
REAL OUTPUT FOR THOSE INPUT
Posted: Fri Jan 09, 2004 2:35 pm
Posted: 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)
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:
for i:=1 to n do begin
if not odd(n1) then inc(n1);
while n1<=n2 do begin
if d[n1] then inc(counter);
Posted: 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.
Posted: 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.
Posted: 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
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.
Posted: Wed Feb 18, 2004 12:14 am
i'm having wa... probably a small mistake, i'll look at it more attentively
10533 - Digit Primes
Posted: Mon Jun 14, 2004 2:57 pm
I can not understand what is the wrong with it.Have there any critical input?
Posted: Tue Jun 15, 2004 8:59 am
Do you think this portion will work correct...
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...
All the part of your code seem correct. Cut the code if you get AC.
Posted: Tue Jun 15, 2004 4:11 pm
Thanks Rajib. At last i have got AC.
10533. Digit prime . Why TLE .. Somebody help me plzzzzz
Posted: Sun Jul 04, 2004 1:53 pm
i m getting time limit exceed . plz help me i dont know y
bool checkprime(int num)
flag = 0;
Posted: Sun Jul 04, 2004 3:42 pm
Your prime testing method is highly inefficient. There are posts that has efficient method to test prime.
Posted: Sat Jul 17, 2004 3:30 pm
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.