10419  Sumup the Primes
Moderator: Board moderators
10419  Sumup the Primes
contains the lexicographically smallest expression that sums up to N
What means by "lexicographically smallest"?
Thank you for your reply.
What means by "lexicographically smallest"?
Thank you for your reply.

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:
It should mean that an answer 101+2 "smaller" than 2+101.
As '+'<'0', you should sort lexicographically your primes up to 300 (101,103,107,109,11,113 ...) and when you search an answer, "lexicographically" smaller primes should be earlier and be prefered "lexicographically" bigger primes.
But it seems that the test data for this problem still is incorrect (as it was during contest)
As '+'<'0', you should sort lexicographically your primes up to 300 (101,103,107,109,11,113 ...) and when you search an answer, "lexicographically" smaller primes should be earlier and be prefered "lexicographically" bigger primes.
But it seems that the test data for this problem still is incorrect (as it was during contest)

 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
Yes.
The judge data seems have something wrong.
I always got the wrong answer.
I support some input and output of my program.
Input
Output
The judge data seems have something wrong.
I always got the wrong answer.
I support some input and output of my program.
Input
1000 14
500 13
17 1
9 3
147 3
233 11
0 0
Output
CASE 1:
101+101+103+103+107+107+109+109+11+11+113+13+5+7
CASE 2:
101+101+103+103+11+11+13+13+17+17+2+3+5
CASE 3:
17
CASE 4:
No Solution.
CASE 5:
101+17+29
CASE 6:
101+11+11+13+13+17+17+19+19+5+7
you guys might be right that the judge's input data isn't OK, but what bothers me more at the moment is that I am getting TLE... my prog gives the right answer for all the input seen on the forum or in the description, so I guss it is "just" slow  what could the problem be? I am using a backtracking method, should I try to come up with something smarter than that?
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
donno to be honest, since I get TLE... but since there are no accepted solutions, I would assume so...route wrote:do you mean that the judge now is still wrong?
other:
since my last post, I have tested my program for all the 14000 case and using a primitive timing (difftime), my prog ran in 10.00 seconds... thus I just can't see what the matter could be... If someone would be willing to look at my code to help me out, I would appreciate it  don't wanna post it here, since it's a realtively fresh problem :)
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

 New poster
 Posts: 28
 Joined: Wed Jul 31, 2002 10:33 am
 Location: Ukraine
 Contact:

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
I am sorry
Hello,
I am extremely sorry that the problem had a mistake. A similar problem was used in a contest in Bangladesh. But when I changed the problem statement I did not recode the solution but tried to modify the existing code and forgot to modify in some places.
I am used backtracking method with some bounding and in this way the problem can be solved within 64kb Memory limit . I hope the data will be updated soon and the problems will be rejudged. So until u see that some people has got this problem accepted don't waste your time on it.
I am extremely sorry that the problem had a mistake. A similar problem was used in a contest in Bangladesh. But when I changed the problem statement I did not recode the solution but tried to modify the existing code and forgot to modify in some places.
I am used backtracking method with some bounding and in this way the problem can be solved within 64kb Memory limit . I hope the data will be updated soon and the problems will be rejudged. So until u see that some people has got this problem accepted don't waste your time on it.
pls, could somebody help me now that the judge is judging correctly? I keep on getting TLE, though I dinamically store the results from previous calculations and limit the obviously impossible cases (when the value of t is less than 4). I have a feeling that I might not deel correctly with the input that my program doesn't terminate, or I am seriously stuck.... pls, help, I can't sleep!!!
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Don't make stringcompare all the time.
I avoid it in this way:
I sort the primes indirectly with an indexarray ind[]. After sorting in ind[0] is the index of the lexicographically smallest prime.
Then I don't store the string representation, I store only these indices. For comparison between two lists of indices you need a function that returns the difference between the first values in the lists that differ.
I avoid it in this way:
I sort the primes indirectly with an indexarray ind[]. After sorting in ind[0] is the index of the lexicographically smallest prime.
Then I don't store the string representation, I store only these indices. For comparison between two lists of indices you need a function that returns the difference between the first values in the lists that differ.

 New poster
 Posts: 24
 Joined: Mon Feb 24, 2003 5:08 pm
I got WA all the time
Can anybody give me test data?
My code is here:
Can anybody give me test data?
My code is here:
Code: Select all
#include <iostream.h>
#include <string.h>
int pr[70],kol=0;
char spr[70][5];
void makepr()
{
int i,j;
pr[0]=2;kol++;
for (i=3;i<300;i+=2)
{
int ok=0;
for (j=0;pr[j]*pr[j]<=i;j++)
if (i%pr[j]==0) {ok=1;break;}
if (ok==0) {pr[kol]=i;kol++;}
}
}
int c[70];
void sort(int *pr1,int kol1,int *c)
{
int i,j;
char s1[5];
for (i=0;i<kol1;i++)
{
int h=pr1[i];
int l=0;
c[i]=i;
while (h>0)
{
s1[l]=char(h%10+'0');
h/=10;
l++;
}
s1[l]=0;
for (j=0;j<l;j++)
spr[i][j]=s1[lj1];
spr[i][l]=0;
}
for (i=0;i<kol1;i++)
for (j=i+1;j<kol1;j++)
if (strcmp(spr[c[i]],spr[c[j]])>0)
{
int h=c[i];
c[i]=c[j];
c[j]=h;
}
int pr2[70];
memcpy(pr2,pr1,70*sizeof(pr1[0]));
for (i=0;i<kol1;i++)
pr1[i]=pr2[c[i]];
}
int a[1001][15];
int f[1001][15][70];
int q[16000][2],end=0;
int c1[70];
int main()
{
makepr();
sort(pr,kol,c);
int i,j,k,n,t;
for (i=0;i<=1000;i++)
for (j=0;j<15;j++)
{
a[i][j]=1;
}
a[0][0]=0;
q[0][0]=0;q[0][1]=0;end=1;
for (i=1;i<=61;i++)
{
f[0][0][i]=2;
}
f[0][0][0]=1;
memcpy(c1,f[0][0],70*sizeof(c1[0]));
for (i=0;i<=61;i++)
{
f[0][0][i]=c1[c[i]];
}
while (end>0)
{
i=q[end1][0],j=q[end1][1];
int p=0;
for (k=0;k<kol;k++)
if (f[i][j][k]>0)
if (i+pr[k]<1001 && j+1<15)
if (a[i+pr[k]][j+1]==1)
{
a[i+pr[k]][j+1]=i;
memcpy(f[i+pr[k]][j+1],f[i][j],70*sizeof(f[0][0][0]));
f[i+pr[k]][j+1][k];
q[end][0]=i+pr[k];
q[end][1]=j+1;
end++;
p=1;
break;
}
if (p==0) end;
}
int r=0;
cin>>n>>t;
while (n!=0 && t!=0)
{
r++;
cout<<"CASE "<<r<<":\n";
int ans[15],l=0;
if (a[n][t]==1) cout<<"No Solution.\n";
else
{
while (n>0)
{
ans[l]=na[n][t];l++;
n=a[n][t];t;
}
sort(ans,l,c1);
cout<<ans[0];
for (i=1;i<l;i++)
cout<<"+"<<ans[i];
cout<<"\n";
}
cin>>n>>t;
}
return 0;
}

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10419 driving me nuts
Can someone verify my output? This problem is driving me crazy
input:
output:
Just tell me if I'm right or wrong.
input:
Code: Select all
32 3
47 5
91 4
140 6
199 13
267 11
301 5
444 7
611 9
789 11
921 5
0 0
Code: Select all
CASE 1:
11+19+2
CASE 2:
11+11+13+5+7
CASE 3:
11+11+2+67
CASE 4:
101+11+11+3+7+7
CASE 5:
11+11+13+13+17+17+19+19+23+3+3+43+7
CASE 6:
101+101+11+11+13+3+3+5+5+7+7
CASE 7:
101+101+11+17+71
CASE 8:
101+101+103+103+11+2+23
CASE 9:
101+101+103+103+107+11+11+13+61
CASE 10:
101+101+103+103+107+107+109+11+11+13+23
CASE 11:
101+101+149+277+293

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Mail me
Ok! Mail me your code little joey.
 A lazy problemsetter
 A lazy problemsetter