OJ Board

Posted: **Tue Jul 29, 2003 2:23 pm**

Could anyone tell me what is the answer for this input?

1 1000000

I've got 30123 but I've got WA ....

Best regards
DM

Posted: **Tue Jul 29, 2003 3:11 pm**

i think there is no input like that, maximum is 999999

try this input :

Code: Select all

output should be : (according to my ACC prog)

Code: Select all

hope this helps.

regards,

titid

Posted: **Tue Jul 29, 2003 3:54 pm**

could you tell me a way to avoid tle for this problem???

Posted: **Tue Jul 29, 2003 4:08 pm**

titid, I got the same results .... as you ...
hmmm I don't know what can I do wrong ...
Could I send you my code ?

anapum: use DP

Best regards
DM

Posted: **Thu Jul 31, 2003 3:12 pm**

the first number and the second number can be change
like this:
999999 1

Posted: **Thu Jul 31, 2003 3:31 pm**

I don't think so ... I don't consider such case and in problem description is sentence which clearly tell us, that first number is not greater than second ....

Best regards
DM

Posted: **Sat Aug 02, 2003 5:30 pm**

To Dominik:

My ACed programme also doesn't consider the case that t2<t1;
try these two test cases:

Input:
39025 489248
3387 67184

Output:
14155
2610

One thing more,did you use long type for N?N can also be as large as 500000.

Hope this can help.

Posted: **Sun Aug 17, 2003 11:55 am**

i m also getting tle with this problem .Can any one tell me briefly an efficient way to solve the problem.

Posted: **Tue Aug 19, 2003 5:50 am**

Dear Faizur,

A few hints for an efficient solution of Shahriar’s problem „Digit Primes“ (10533). I’ve just started working on the program ... these are the major parts of my „design“:

1.)
To count the number of „Digit Primes“ within the range [t1, t2] means to first check if the number is prime and then to check the digit sum being prime (which is the „weaker sieve“). For both activities You need a look up table of the prime numbers up to t2 which can be produced by using the „sieve of Eratosthenes“. Note that you only have to strike out the multiples of the primes up to sqrt(t2) to get the complete look up table of all prime numbers up to t2. I think performing this once for a t2_max=999999 should be fine for this problem.

2.)
You should also use an efficient algorithm to calculate the digit sum – try this one:

[c]int digit_sum(int number)

{ int sum = 0;
do
{
sum += number;
number /= 10;
sum -= number*10;
} while (number);
return sum;
}[/c]
3.)
Perhaps some of the input case ranges overlap and performing some bookkeeping for reusing ranges which have already been checked might pay off.

Yours, Eric

Posted: **Wed Aug 20, 2003 5:18 am**

Sorry folks,

I have to revise my own posting after a few learning cycles with TLE. I finally got AC (1.664 seconds). Here some new (and better) hints:

A.) Forget the algorithm for calculating the digit sum! When going up through the odd numbers (3,5,7, ...) and checking for digit primes you can keep track of the digit sum in parallel.

B.) The look up table containing TRUE for digit primes and FALSE for the rest has to be "integrated" (once) to prevent having to loop from t1 to t2 for each input case. This can be done in parallel with the loop in (A) and then the number of digit primes is generally the expression:

(integrated_list[t2] - integrated_list[t1-1])

... where integrated_list[] is an array starting with the counter value 0 and incrementing at each index of a digit prime.

Yours, Eric

Posted: **Fri Aug 22, 2003 1:45 pm**

Thank u Eric for ur help.I need to rethink about the problem

Posted: **Mon Oct 13, 2003 9:16 pm**

Can you guys tell me, why on earth this program gets RTE(Floating point Exception)...I am totally depressed seeing this message again & again...

please someone help me out...

At last I got AC...I had to change my prime generating function...

thanks guys

Code: Select all

Deleted

Razib

Posted: **Tue Oct 14, 2003 6:28 am**

Hi razibcse!

The only floating point operation I can see at a first glance is the sqrt() function. I assume you passed a "very large" (and therefore overflowed to negative) 'long' argument to sqrt(). Watch out for the range you are using.

Yours, Eric

Posted: **Tue Oct 14, 2003 8:08 am**

Finally I got Acc

Best regards
DM

Posted: **Mon Nov 03, 2003 7:44 am**

Cound anyone help with my code? ><"
I try many cases, but still can't find the problem.

Code: Select all

#include<stdio.h>

typedef struct {
	int digitprimestate;
	long key;
}NUM;

NUM array[1000002];

int primestate[1000002];
long getdigitnum(long n);

int main()
{
	long digitprimecount = 2;
    long cases;
    long left,right;
    long i,j;
    
	primestate[1] = 0;
	array[1].digitprimestate = 0;
	array[1].key = 0;

	primestate[2] = 1;
	array[2].digitprimestate = 1;
	array[2].key = 1;

	primestate[3] = 1;
	array[3].digitprimestate = 1;
	array[3].key = 2;

	primestate[4] = 0;
	array[4].digitprimestate = 0;
	array[4].key = 2;

    for(i=5;i<1000000;i+=2){
        for(j=3;j*j<=i;j+=2)
            if(i%j==0) break;
		if(i%j!=0){
            primestate[i]=1;
			if( primestate[ getdigitnum(i) ] == 1 ){
				array[i].digitprimestate = 1;
				array[i].key = ++digitprimecount;
			}
		}
		else{
			array[i].digitprimestate = 0;
			array[i].key = digitprimecount;			
		}
		array[i+1].digitprimestate = 0;
		array[i+1].key = digitprimecount;
    }

    scanf("%ld",&cases);
    while(cases-->0){        
        scanf("%ld %ld",&left,&right);
        printf("%ld\n",array[right].key - array[left-1].key);
    }
    
    return 0;
}

long getdigitnum(long n){
    long a=0;
    for(;n;n/=10)
        a+=n%10;
    return a;
}

OJ Board

10533 - Digit Primes

10533 - Digit Primes