10419 - Sum-up the Primes

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

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Sat Feb 16, 2008 9:02 am

Sample Input:
20 10
0 0

Sample Output
CASE 1:
No Solution.

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

Post by rezaeeEE » Thu Feb 28, 2008 1:49 pm

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
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 10419 - Sum-up the Primes

Post by Farsan » Sun Feb 16, 2014 6:41 pm

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
Last edited by Farsan on Sat Jan 03, 2015 9:40 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10419 - Sum-up the Primes

Post by brianfry713 » Tue Feb 18, 2014 10:47 pm

Read this thread.
Try using printf instead of cout.
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10419 - Sum-up the Primes

Post by Mukit Chowdhury » Thu Sep 04, 2014 3:39 pm

Getting TLE... Help please... :(

Code: Select all

		
Accepted
Last edited by Mukit Chowdhury on Sun Jun 18, 2017 4:41 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10419 - Sum-up the Primes

Post by brianfry713 » Thu Sep 04, 2014 7:43 pm

Read this thread.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: He He

Post by lighted » Tue Jun 27, 2017 6:00 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 104 (10400-10499)”