Page 4 of 4
Posted: Sat Feb 16, 2008 9:02 am
Sample Input:
20 10
0 0

Sample Output
CASE 1:
No Solution.

### help

Posted: 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

### Re: 10419 - Sum-up the Primes

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

Code: Select all

``````ACED
some tips
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
Try using printf instead of cout.

### Re: 10419 - Sum-up the Primes

Posted: Thu Sep 04, 2014 3:39 pm

Code: Select all

``````
Accepted
``````

### Re: 10419 - Sum-up the Primes

Posted: Thu Sep 04, 2014 7:43 pm