10948 - The primary problem

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

Moderator: Board moderators

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

10948 - The primary problem.

Post by Junayeed » Sat Oct 22, 2005 7:37 am

I think this problem is prety easy, but i am getting WA.

plaese help with some tricky input.

Thanks
Junayeed

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Oct 22, 2005 8:00 am

Nothing tricky, just some boundary cases:

Code: Select all

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
999980
999981
999982
999983
999984
999985
999986
999987
999988
999989
999990
999991
999992
999993
999994
999995
999996
999997
999998
999999
1000000
0
Output:

Code: Select all

4:
2+2
5:
2+3
6:
3+3
7:
2+5
8:
3+5
9:
2+7
10:
3+7
11:
NO WAY!
12:
5+7
13:
2+11
14:
3+11
15:
2+13
16:
3+13
17:
NO WAY!
18:
5+13
19:
2+17
20:
3+17
999980:
19+999961
999981:
2+999979
999982:
3+999979
999983:
NO WAY!
999984:
5+999979
999985:
2+999983
999986:
3+999983
999987:
NO WAY!
999988:
5+999983
999989:
NO WAY!
999990:
7+999983
999991:
NO WAY!
999992:
13+999979
999993:
NO WAY!
999994:
11+999983
999995:
NO WAY!
999996:
13+999983
999997:
NO WAY!
999998:
19+999979
999999:
NO WAY!
1000000:
17+999983

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Sat Oct 22, 2005 2:27 pm

my output are prety much same...except one

for 999983 it gives me the following output
0+999983

thanks for the help
Junayeed

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Sat Oct 22, 2005 2:59 pm

OK..i got AC now..thanks everybody
Junayeed

rafi6047
New poster
Posts: 3
Joined: Tue Oct 10, 2006 5:02 pm

10948 - The primary problem

Post by rafi6047 » Tue Oct 10, 2006 5:08 pm

someone pls help me out. im getting wa with this code, i've tried so many test cases, all the outputs r right. but still gettin wa. pls help.




#include<iostream.h>
#include<math.h>


#define P 1000002


bool prime[P];


int main()
{
int i,j;

prime[0]=prime[1]=1;

for(i=2; i<=sqrt(P-1); i++)
{
if(prime==0)
{
for(j=i*i; j<=P-1; j=j+i)
{
prime[j]=1;
}
}
}


while(cin>>i)
{

if(i==0) break;


for(j=2;j<=i/2;j++)
{
if( (prime[j]==0) && (prime[i-j]==0) ) break;

}

if(j>(i/2)) cout<<"NO WAY!\n";

else
{
cout<<i<<":\n"<<j<<"+"<<(i-j)<<"\n";
}

}
return 0;
}

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10948 pls help

Post by tan_Yui » Tue Oct 10, 2006 7:01 pm

Hi,
your code didn't return N itself as a part of output, if N cannot be represented as the sum of two prime number.
Please check your output format carefully. :)

Best regards.

rafi6047
New poster
Posts: 3
Joined: Tue Oct 10, 2006 5:02 pm

Post by rafi6047 » Wed Oct 11, 2006 7:04 am

thnx tan_yui. got AC. thnx very much.

bishop
New poster
Posts: 43
Joined: Fri May 04, 2007 12:57 pm

soorry

Post by bishop » Wed Jul 11, 2007 9:15 pm

sorry

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

10948(Primary Problem)--TLE

Post by ishtiaq ahmed » Thu Jul 26, 2007 8:37 pm

Can anybody help me? I am facing TLE (10.035s). Here is my code

Code: Select all

cut after ac
Please try to help me.
Last edited by ishtiaq ahmed on Fri Jul 27, 2007 4:00 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Jul 27, 2007 2:35 am

Code: Select all

      if(!flag)
      {
         for(i=temp;i>=(number/2);i-=2)
         {
            if(!data[i])
            {
               for(j=3;i+j<=number;j+=2)     <--- ??? why do you need this loop ? 
               {
                  if(!data[j] && i+j==number)
                  {
                     flag=1;
                     printf("%ld:\n",number);
                     printf("%ld+%ld\n",j,i);
                     break;
                  }       
----
Rio

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

post reply of previous submission of 10948

Post by ishtiaq ahmed » Fri Jul 27, 2007 7:15 am

Thanks rio for replying me.
At first i have generated the prime number upto 1000000. When the input is 18 output will

Code: Select all

18 = 5 + 13;
Firstly i have checked any given number that is greater than 4 even or not. if it is even subtracted it with 1, otherwise 2.

so the number is now 17(temporarily).

then i checked if 2+17==18? if not then enter The first for loop. first for loop handled data from 17 to ...............->(18/2);and as well as the second one that is asked by rio handled data from 3 to(18/2).
Now let see..

Code: Select all

3+17 == 18 (no) (3+17=20 exceeds 18) then
skip checking 3+15== 18. Because 15 is not prime. then
3+13 == 18 (no) (3+13=16< 18)so
5+13 == 18. Then stop and print the result.
So these for two for loops are incremented or decremented by 2.

I think you understand my algorithm. If there any efficient algorithm let me know and also try to find my errors in this code.
Last edited by ishtiaq ahmed on Fri Jul 27, 2007 4:01 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Jul 27, 2007 8:07 am

Yes, I could understand your algorithm, and it is efficient enough.
Few things to say.

1. Actually, you don't need the loop which I mentioned.

Code: Select all

               for(j=3;i+j<=number;j+=2)
               {
                  if(!data[j] && i+j==number)
                  {
                     flag=1;
                     printf("%ld:\n",number);
                     printf("%ld+%ld\n",j,i);
                     break;
                  }      
               }
Look careful. if-block is executed at most once, when j = number - i is a prime.
This waste loop is causing TLE.

2. Its not "NO WAY", but "NO WAY!"

3. 1 is not a prime.

Hope this helps.
----
Rio

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

post reply of previous submission of 10948

Post by ishtiaq ahmed » Fri Jul 27, 2007 3:59 pm

A lot of thanks to rio. Now i get ac. Hope you will help me in future.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

AbiusX
New poster
Posts: 1
Joined: Sat Aug 18, 2007 8:25 pm
Location: Tehran, iran
Contact:

:( WA

Post by AbiusX » Sat Aug 18, 2007 8:39 pm

the same code i used for 543 (Goldbach) dunno watz wrong getting a WA ;)

Code: Select all

#include<iostream>
using namespace std;

#define RANGE 1000010
#define sqrtRANGE 1010
int isprime[RANGE];
int prime[RANGE/10];
int primecount;

inline void primesieve()
{
       unsigned int i,j;
       for (i=0;i<RANGE;++i)
           isprime[i]=i&1;
       isprime[2]=1;
       isprime[1]=0;
       
       for (i=3;i<=sqrtRANGE;i+=2)
           if (isprime[i])
           for (j=i*i;j<RANGE;j+=i*2)
               isprime[j]=0;

               primecount=0;
       for (i=0;i<RANGE;++i)
           if (isprime[i]) 
           {
                           isprime[i]=primecount;
                           prime[primecount++]=i;
           }
//           cout <<primecount<<endl;
}


int main()
{
    primesieve();
    int n,i,j,a,b;
    while(cin>>n,n)
    {
                   a=0;
                   b=n-1;
                   while (!isprime[b]) b--;
                   b=isprime[b];
                   while (prime[b]+prime[a]!=n && a<=b)
                   {
                         while (prime[b]+prime[a]>n) 
                         {
                               b--;
                         }
                         while (prime[b]+prime[a]<n)
                         {
                                a++;
                         }
                                
                         if (prime[b]+prime[a]!=n) a++;
                   }
                   if (a<=b)
                      cout <<n<<":"<<endl<<prime[a]<<"+"<<prime[b]<<endl;
                   else
                   {
//                       cout <<n<<endl;
                       cout<<n<<":"<<endl<<"NO WAY!"<<endl; //never happens!
                   }
    }                     
    return 0;
}
tQ

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

Post by sapnil » Tue Oct 09, 2007 8:32 am

Try this case:

Code: Select all

Input:
1000000
999999
99999
1
2
3
11
121
100
Output:
1000000:
17+999983
999999:
NO WAY!
99999:
NO WAY!
1:
NO WAY!
2:
NO WAY!
3:
NO WAY!
11:
NO WAY!
121:
NO WAY!
100:
3+97
Thanks
Keep posting
Sapnil

Post Reply

Return to “Volume 109 (10900-10999)”