Page 5 of 8

hi hamedv

Posted: Wed Jul 25, 2007 7:20 am
by ishtiaq ahmed
i think its not needed to close the bracket as you have said. It works the same as you think.

Thank you for your reply.

Posted: Wed Jul 25, 2007 7:39 am
by newton
mr ishtiaqq,

you needn't count upto i<SIZE for the outer loop.
if you replaced:

Code: Select all

the condition i<SIZE
into:
i<= sqrt(SIZE)

it will work good as you want.

WA-10533(prime digit)

Posted: Wed Jul 25, 2007 11:24 am
by ishtiaq ahmed
I have updated my code as follows. Firstly it faced TLE and then as follows. Please try to help me.

Code: Select all

#include<stdio.h>
#include<math.h>

#define SIZE 1000001

long  a,b,data[SIZE]={0},add[SIZE]={0};


void s (void);
long sum_prime(void);


int main()
{
	long k,i,result,cas,sum=0,z,dum,m;
	s();
	sum=0;
	for(i=0;i<SIZE;i++)
	{
		if(!data[i])
		{
			z=i;dum=0;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
			{
				sum++;
				add[i]=sum;
			}
		}
		else
			add[i]=sum;
	}
	scanf("%ld",&cas);
	for(k=1;k<=cas;k++)
	{
		scanf("%ld %ld",&a, &b);
		result=sum_prime();
		printf("%ld\n",result);
	}
	return 0;
}



void s(void)
{
	long i,j,sqrtNum;
	data[0]=1;
	data[1]=1;
	for(i=4;i<SIZE;i+=2)
		data[i]=1;
	sqrtNum = (long)sqrt(SIZE);
	for(i=3;i<sqrtNum;i+=2)
		for(j=i;i*j<SIZE;j++)
			if(!data[i*j])
				data[i*j]=1;
}



long sum_prime(void)
{
	long XX,z,dum,m;
	if(a!=b)
		XX=add[b]-add[a];
	else if(a==b)
	{
		if(!data[a])
		{
			dum=0;z=a;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
				XX=1;
		}
		else
			XX=0;
	}
	return XX;
}

Posted: Wed Jul 25, 2007 2:13 pm
by Jan
What if you use add - add[a-1] ?

post reply of previous submission of 10533

Posted: Wed Jul 25, 2007 4:46 pm
by ishtiaq ahmed
Jan bhia was written

Code: Select all

What if you use add[b] - add[a-1] ?
Let there are 10 data in the array as follows

Code: Select all


            1  2  3  4  5  6  7  8  9  10
            |  |  |  |  |  |  |  |  |  |
            N  P  P  N  P  N  P  N  N  N
here

Code: Select all


     N-> Not prime
     P-> Prime & have prime digit
Now i consider that if data is prime and the prime data's summation of didits are prime then i add them just like these

Code: Select all


            1  2  3  4  5  6  7  8  9  10
            |  |  |  |  |  |  |  |  |  |
            N  P  P  N  P  N  P  N  N  N
     add[]->0  1  2  2  3  3  4  4  4  4
Now when i am asked to find out the total summation that is asked by this problem tryed to solve like this:-

Code: Select all

Question: Find the total answer from 5th[a] element to 10th[b] element?
answer:  add[b-1] - add[a-1] that is 
         add[9] - add[4]

Code: Select all

Question: Find the total answer from 4th[a] element to 4th[b] element?

answer: First i have checked if the 4th element is prime and have prime digit then i printed 1 otherwise 0;  

Re: 10533 - Digit Primes

Posted: Sat May 17, 2008 8:53 am
by mukit
Someone can plesae tell me why I'm getting TLE ?
I read previous posts.
Here is my code :

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;

#define SIZE 1000002

long  a,b,i,j;
char data[SIZE]={0};
int dp[SIZE];
int nop[SIZE];
void sieve(void)
{
   int i, j, k;

   data[0] = 1;
   data[1] = 1;

   for (i=4; i<SIZE; i+=2)
   {
      data[i] = 1;
   }

   for (i=3; i<SIZE; i+=2)
   {
      if (!data[i])
      {
         k = SIZE / i;
      
         for (j=i; j<=k; j+=2)
         {
            data[i * j] = 1;
         }
      }

   
   }
}
void is_dp()
{
	long x,z,ct=0,du,m=0;
	for(i=0;i<SIZE;i++)
	{
		if(!data[i])
		{
			z=x=i;
			du=0;
			while(z)
			{
				m=z%10;
				du+=m;
				z/=10;
			}
			if(!data[du])
			{
				dp[i]=1;
			}
		}
	}
}
void sum_prime()
{
	int sum=0,dum,m=0,z;
	for(i=0;i<=SIZE;i++)
	{
		if(dp[i])
		{
			sum+=1;
		}
		nop[i]=sum;
	}
}
int main()
{
	long test;
	sieve();
	is_dp();
	sum_prime();
	cin >> test;
	for(long i=0;i<test;i++) 
	{
		cin>>a>>b;
		cout<<nop[b]-nop[a-1]<<endl;
	}
	return 0;
}


Thank's in advance.

Re: 10533 - Digit Primes

Posted: Sun May 18, 2008 10:39 am
by emotional blind
probably your is_dp function is costly. try to re-implement this is_dp using something real dp :P
Something like this -

Code: Select all

	int ds[SIZE];
	int dsum(int n){
		int &ret = ds[n];
		if(-1!=ret)return ret;

		if(n<10)return ret=n;

		return ret = n%10 + dsum(n/10);
	}

	void is_dp(){
		long x,z,ct=0,du,m=0;
       memset(ds,-1,sizeof(ds));

		for(i=0;i<SIZE;i++)
       {
          if(!data[i])
          {
             du = dsum(i);
			 if(!data[du])
             {
                dp[i]=1;
             }
          }
       }	
	}

Re: 10533 - Digit Primes

Posted: Sun May 18, 2008 12:56 pm
by mukit
To emotional Blind,
I did as you said but got TLE again with running time 3.00 sec like past. :oops:
I did it as :

Code: Select all

Removed after AC
Thanks for reply.

Re: 10533 - Digit Primes

Posted: Mon May 19, 2008 3:26 am
by emotional blind
now, try again with replacing all cin-cout with scanf-printf.

Re: 10533 - Digit Primes

Posted: Mon May 19, 2008 3:38 pm
by mukit
Thank's a lot emotional blind. I got AC with 0.56 sec. :D
But something was ambiguous to me. It didn't find the memset() function in ANSI C with header #include<stdio.h> and
only #include<cstdio> header in C++. I had to use #include<iostream> with namespace. :-?
Another thing why it took such a huge time(3.00) with cin-cout getting TLE?

After all thank you very much. :D

Re: 10533 - Digit Primes

Posted: Tue May 20, 2008 4:21 am
by emotional blind
mukit wrote:Thank's a lot emotional blind. I got AC with 0.56 sec. :D
You are welcome.
mukit wrote: It didn't find the memset() function in ANSI C with header #include<stdio.h>
#include <string.h>
mukit wrote: Another thing why it took such a huge time(3.00) with cin-cout getting TLE?
cin and cout is lot more costly than scanf and printf, this is noticeable for the problems which needs large input and output data to handle.
I think it takes more than 3.00 seconds. though 3.00 is the time limit, after 3.00 seconds the judge system terminates your program.

10533 - Digit Primes

Posted: Wed Jul 02, 2008 1:24 pm
by lnr
Ishtiaq Ahmed wrote:
Jan bhia was written
Edit!!!!!!

10533 - Digit Primes

Posted: Wed Jul 02, 2008 1:30 pm
by lnr
emotional blind wrote:
cin and cout is lot more costly than scanf and printf, this is noticeable for the problems which needs large input and output data to handle.
I think it takes more than 3.00 seconds. though 3.00 is the time limit, after 3.00 seconds the judge system terminates your program.
Why cin and cout are costly?
Would someone please tell about the use of memset()?
  • The header file.
    How to use it.

Re: 10533 - Digit Primes

Posted: Mon Jul 21, 2008 12:23 pm
by shekhar
PLZZ Help...I am Getting TLE in this problem
I used sieve for prime & dprime.Current sieve takes around 0.2-0.3 seconds for calculation.Can anyone help me out...how optimization can be done??
Here is my code...

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
bool prime[1000001];
bool dprime[1000001];
void seive()
{
     int m=1000;
     memset(prime,true,sizeof(prime));
     prime[0]=false;
     prime[1]=false;
     for(int i=2;i<=m;i++)
     if(prime[i]) 
     for(int k=i*i;k<=1000000;k+=i)
                  prime[k]=false;
                  
     memset(dprime,false,sizeof(dprime));
     dprime[0]=false;
     dprime[1]=false;
     for(int j=2;j<=1000000;j++)
     {
             int sum=0,num=j;
             while(num>=1)
             {
                          sum+=num%10;
                          num=num/10;
             }
             if(prime[sum])
             dprime[j]=true;
     }        
}
int main()
{
    int test,a,b;
    seive();
    scanf("%d",&test);
    while(test--)
    {
              scanf("%d %d",&a,&b);
              int n,count=0;
              for(n=a;n<=b;n++)
              {
                               if(prime[n] && dprime[n])
                               count++;                              
              }
              printf("%d\n",count);
    }
    system("pause");
}

Re: 10533 - Digit Primes

Posted: Mon Jul 28, 2008 11:44 am
by Obaida
Some one please help me to get Acc less TLE. I tried but failed so many times.

Code: Select all

removed