Sample Input:
20 10
0 0
Sample Output
CASE 1:
No Solution.
10419 - Sum-up the Primes
Moderator: Board moderators
help
thanks DP.
but still WA.
thanks
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;
}
Re: 10419 - Sum-up the Primes
Frustating...TLE
![:(](./images/smilies/icon_frown.gif)
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10419 - Sum-up the Primes
Read this thread.
Try using printf instead of cout.
Try using printf instead of cout.
Check input and AC output for thousands of problems on uDebug!
-
- Learning poster
- Posts: 99
- Joined: Fri Aug 17, 2012 9:23 pm
- Location: Dhaka
- Contact:
Re: 10419 - Sum-up the Primes
Getting TLE... Help please...
![:(](./images/smilies/icon_frown.gif)
Code: Select all
Accepted
Last edited by Mukit Chowdhury on Sun Jun 18, 2017 4:41 pm, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10419 - Sum-up the Primes
Read this thread.
Check input and AC output for thousands of problems on uDebug!
Re: He He
Sum up the primes (II) 10447 solved by DP.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.
![:D](./images/smilies/icon_biggrin.gif)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman