## 10419 - Sum-up the Primes

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
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

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

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
``````
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

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

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

Check input and AC output for thousands of problems on uDebug!

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

### Re: He He

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 , so think in that direction.
Sum up the primes (II) 10447 solved by DP.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman