Page 4 of 4

Posted: Sat Feb 16, 2008 9:02 am
by DP
Sample Input:
20 10
0 0

Sample Output
CASE 1:
No Solution.

help

Posted: Thu Feb 28, 2008 1:49 pm
by rezaeeEE
thanks DP.

but still WA.

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
//#include <fstream>

using namespace std;

//fstream fout( "out.txt" );

const int ted = 62;
int prime[ted], n, t;
string p[ted];
int q, dp[68][17][1010];
bool pr[301] = {0};

int solve( int ptr, int cnt, int sum ){
   if( ptr >= 62 || sum < 0 || cnt < 0 )
      return 0;
   if( dp[ptr][cnt][sum] != -1 )
      return dp[ptr][cnt][sum];
   if( !cnt )
      return dp[ptr][cnt][sum] = ( sum == 0 ) ? -2 : 0;
   if( ptr != q ){
      if( solve( ptr + 1, cnt - 2, sum - 2 * prime[ptr] ) )
         return dp[ptr][cnt][sum] = 2;
   }
   if( solve( ptr + 1, cnt - 1, sum - prime[ptr] ) )
      return dp[ptr][cnt][sum] = 1;
   if( solve( ptr + 1, cnt, sum ) )
      return dp[ptr][cnt][sum] = -2;
   return dp[ptr][cnt][sum] = false;
}

int main()
{
   int cnt = 0;
   memset( dp, -1, sizeof dp );
   for( int i = 2; i < 301; i++ )
      if( !pr[i] ){
         prime[cnt++] = i;
         for( int j = 2 * i; j < 301; j += i )
            pr[j] = true;
      }
   for( int i = 0;i < ted; i++ ){
      int temp = prime[i];
      while( temp )
         p[i] = char( temp % 10 + '0' ) + p[i], temp /= 10;
   }
   for( int i = 0;i < ted; i++ )
      for( int j = i + 1; j < ted; j++ )
         if( p[i] > p[j] ){
            swap( prime[i], prime[j] );
            swap( p[i], p[j] );
         }
   for( int i = 0;i < ted; i++ )
      if( prime[i] == 2 ){
         q = i;
         break;
      }
   int test = 1;
   while( cin >> n >> t, n || t ){
      int can = solve( 0, t, n );
      cout << "CASE " << test++ << ":\n";
      int first = 1;
      if( !can )
         cout << "No Solution.\n";
      else{   
         int tptr = 0, tcnt = t, tsum = n;
         while( tsum  ){
            int tp = dp[tptr][tcnt][tsum];
            if( tp == -2 )
               tp = 0;
            for( int i = 0;i < tp; i++ ){
               if( !first )
                  cout << '+';
               first = 0;
               cout << prime[tptr];
            }
            tsum -= tp * prime[tptr];
            tptr++;
            tcnt -= tp;
         }
         cout << endl;
      }
   }
   return 0;
}
thanks

Re: 10419 - Sum-up the Primes

Posted: Sun Feb 16, 2014 6:41 pm
by Farsan
Frustating...TLE :(

Code: Select all

ACED
some tips
1.use printf instead of cout
2.do not convert prime numbers to string at every comparison.i converted every prime numbers to string before comparison and then sorted the numbers with respect to string

Re: 10419 - Sum-up the Primes

Posted: Tue Feb 18, 2014 10:47 pm
by brianfry713
Read this thread.
Try using printf instead of cout.

Re: 10419 - Sum-up the Primes

Posted: Thu Sep 04, 2014 3:39 pm
by Mukit Chowdhury
Getting TLE... Help please... :(

Code: Select all

		
Accepted

Re: 10419 - Sum-up the Primes

Posted: Thu Sep 04, 2014 7:43 pm
by brianfry713
Read this thread.

Re: He He

Posted: Tue Jun 27, 2017 6:00 pm
by lighted
shahriar_manzoor wrote: Sat Apr 26, 2003 8:49 am When I made Sumup the primes I intended people to use backtracking with constraints to solve this problem but they got away with more conventional dynamic programming approach so I have made sum up the primes (II) so they have to use backtracking with constraints to solve this problem :wink:, so think in that direction.
Sum up the primes (II) 10447 solved by DP. :D