10419 - Sum-up the Primes

[DP]

Sample Input:
20 10
0 0

Sample Output
CASE 1:
No Solution.

[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

[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

[brianfry713]

Read this thread.
Try using printf instead of cout.

[Mukit Chowdhury]

Getting TLE... Help please...

Code: Select all

		
Accepted

[brianfry713]

Read this thread.

[lighted]

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 , so think in that direction.

Sum up the primes (II) 10447 solved by DP.