10419 - Sum-up the Primes

[alu_mathics]

I forgot the critical cases.I generated some inputs.Try with this.
Input

Code: Select all

346 10
972 10
645 7
578 10
926 1
996 8
568 4
474 10
407 6
441 12
92 1
183 5
183 14
222 6
765 1
660 1
978 13
731 5
976 5
546 12
471 8
438 9
887 3
744 9
622 1
407 10
770 7
93 6
335 7
755 4
584 13
657 6
377 3
552 9
174 13
53 4
283 7
325 2
625 8
454 8
818 12
638 10
101 3
155 4
994 4
542 2
752 1
662 6
119 10
323 7
304 1
726 13
536 3
106 13
55 10
458 4
408 14
68 10
499 1
123 1
452 5
144 9
670 8
356 11
305 10
353 1
306 9
744 10
83 10
228 8
459 12
602 6
786 2
332 11
807 6
886 5
502 2
94 3
158 1
354 1
300 12
551 9
97 10
867 3
142 6
59 13
735 6
87 13
163 7
288 6
612 2
997 12
5 6
906 7
774 8
553 9
439 1
823 11
67 11
96 8
277 9
627 8
127 7
451 2
910 7
758 13
105 8
899 2
102 1
895 4
304 11
791 1
261 13
666 2
40 10
92 13
842 12
42 6
700 4
288 1
904 6
848 13
365 1
570 4
914 8
548 5
410 7
535 4
411 4
628 11
456 8
820 4
597 14
754 4
249 1
650 1
224 11
428 8
575 14
42 8
455 1
486 11
246 6
164 9
363 5
217 12
558 9
996 13
741 4
186 6
673 2
553 8
713 3
130 6
746 1
998 4
30 8
555 6
862 4
802 10
305 5
77 13
88 9
717 3
545 8
791 7
648 2
979 6
947 2
626 12
806 3
102 11
291 6
598 4
498 2
460 2
720 6
330 12
286 10
237 5
129 2
324 2
77 12
869 4
900 5
155 8
831 1
563 13
150 3

Output:

Code: Select all

CASE 1:
11+11+113+113+13+13+17+17+19+19
CASE 2:
101+101+103+103+107+109+109+113+113+13
CASE 3:
101+101+107+107+109+109+11
CASE 4:
107+11+13+13+167+17+17+181+23+29
CASE 5:
No Solution.
CASE 6:
103+103+107+107+109+113+113+241
CASE 7:
101+103+167+197
CASE 8:
103+11+11+13+13+17+17+257+29+3
CASE 9:
103+19+19+2+23+241
CASE 10:
101+109+109+11+11+13+13+17+17+19+19+2
CASE 11:
No Solution.
CASE 12:
101+3+3+5+71
CASE 13:
11+11+17+17+19+19+2+29+3+31+5+5+7+7
CASE 14:
101+3+3+31+5+79
CASE 15:
No Solution.
CASE 16:
No Solution.
CASE 17:
101+107+109+11+11+113+113+127+127+13+13+131+2
CASE 18:
103+151+157+157+163
CASE 19:
163+2+241+277+293
CASE 20:
101+107+109+109+11+11+13+13+17+17+19+19
CASE 21:
103+107+109+109+11+11+19+2
CASE 22:
103+109+109+11+11+17+17+2+59
CASE 23:
No Solution.
CASE 24:
101+101+103+103+107+107+109+11+2
CASE 25:
No Solution.
CASE 26:
101+109+11+11+127+13+13+17+2+3
CASE 27:
103+107+107+109+109+2+233
CASE 28:
2+3+3+5+7+73
CASE 29:
103+19+23+23+29+67+71
CASE 30:
167+2+293+293
CASE 31:
101+107+11+11+127+127+13+13+17+17+19+19+2
CASE 32:
103+137+137+139+139+2
CASE 33:
101+269+7
CASE 34:
101+101+103+103+107+11+11+13+2
CASE 35:
11+11+17+17+19+19+2+3+3+5+53+7+7
CASE 36:
13+2+31+7
CASE 37:
101+107+17+17+19+19+3
CASE 38:
No Solution.
CASE 39:
103+107+109+109+11+179+2+5
CASE 40:
103+109+11+11+13+17+17+173
CASE 41:
101+103+107+107+109+11+11+113+113+13+13+17
CASE 42:
101+109+109+11+11+127+127+13+13+17
CASE 43:
5+7+89
CASE 44:
101+2+47+5
CASE 45:
229+251+257+257
CASE 46:
271+271
CASE 47:
No Solution.
CASE 48:
103+107+109+109+11+223
CASE 49:
11+11+13+13+2+3+3+5+5+53
CASE 50:
101+107+17+17+19+19+43
CASE 51:
No Solution.
CASE 52:
103+103+107+107+109+11+11+113+13+13+17+17+2
CASE 53:
2+241+293
CASE 54:
No Solution.
CASE 55:
No Solution.
CASE 56:
101+103+13+241
CASE 57:
101+109+11+11+13+13+17+17+19+19+23+23+29+3
CASE 58:
No Solution.
CASE 59:
No Solution.
CASE 60:
No Solution.
CASE 61:
101+103+149+2+97
CASE 62:
17+17+19+19+2+23+3+3+41
CASE 63:
103+107+107+109+109+31+31+73
CASE 64:
103+11+11+113+13+13+17+17+19+2+37
CASE 65:
101+101+11+11+13+13+17+17+19+2
CASE 66:
No Solution.
CASE 67:
107+17+17+19+19+2+23+23+79
CASE 68:
107+109+11+11+113+113+127+127+13+13
CASE 69:
11+11+2+29+3+3+5+5+7+7
CASE 70:
107+17+17+19+19+23+23+3
CASE 71:
101+109+11+11+127+13+13+17+17+19+19+2
CASE 72:
103+103+107+107+109+73
CASE 73:
No Solution.
CASE 74:
101+109+11+11+13+13+17+17+19+19+2
CASE 75:
101+103+127+181+2+293
CASE 76:
163+2+223+227+271
CASE 77:
233+269
CASE 78:
13+2+79
CASE 79:
No Solution.
CASE 80:
No Solution.
CASE 81:
11+11+113+13+13+17+17+19+19+23+3+41
CASE 82:
101+109+109+11+11+13+13+131+53
CASE 83:
11+11+17+2+3+3+31+5+7+7
CASE 84:
281+293+293
CASE 85:
101+23+3+3+5+7
CASE 86:
No Solution.
CASE 87:
101+103+103+157+2+269
CASE 88:
No Solution.
CASE 89:
103+11+13+13+17+3+3
CASE 90:
103+109+11+11+13+41
CASE 91:
No Solution.
CASE 92:
101+101+103+103+107+109+109+11+11+113+127+2
CASE 93:
No Solution.
CASE 94:
103+173+173+179+179+2+97
CASE 95:
101+103+107+107+109+11+157+79
CASE 96:
103+109+109+11+11+113+13+13+71
CASE 97:
No Solution.
CASE 98:
103+107+107+109+109+11+11+13+13+17+223
CASE 99:
No Solution.
CASE 100:
13+23+3+3+37+5+5+7
CASE 101:
101+103+11+11+13+13+17+3+5
CASE 102:
103+107+109+109+11+179+2+7
CASE 103:
3+3+5+5+7+7+97
CASE 104:
No Solution.
CASE 105:
101+103+103+127+191+2+283
CASE 106:
103+109+109+11+11+113+113+127+13+13+17+17+2
CASE 107:
2+3+3+5+5+7+7+73
CASE 108:
No Solution.
CASE 109:
No Solution.
CASE 110:
No Solution.
CASE 111:
11+11+131+19+19+2+23+23+29+29+7
CASE 112:
No Solution.
CASE 113:
11+13+13+17+19+19+23+23+29+29+3+3+59
CASE 114:
No Solution.
CASE 115:
No Solution.
CASE 116:
No Solution.
CASE 117:
101+107+107+109+11+11+113+127+127+13+13+3
CASE 118:
13+13+3+3+5+5
CASE 119:
101+167+199+233
CASE 120:
No Solution.
CASE 121:
103+131+137+137+139+257
CASE 122:
103+107+109+109+11+11+113+113+127+13+13+17+2
CASE 123:
No Solution.
CASE 124:
101+103+167+199
CASE 125:
103+103+107+107+109+109+113+163
CASE 126:
101+103+131+2+211
CASE 127:
103+109+11+11+113+2+61
CASE 128:
101+139+2+293
CASE 129:
101+2+229+79
CASE 130:
103+109+109+11+11+113+13+13+2+71+73
CASE 131:
101+101+103+103+11+11+13+13
CASE 132:
163+277+283+97
CASE 133:
103+109+109+11+11+127+13+13+17+17+19+2+41+5
CASE 134:
101+263+293+97
CASE 135:
No Solution.
CASE 136:
No Solution.
CASE 137:
107+11+11+13+17+17+19+19+2+3+5
CASE 138:
101+103+107+11+13+13+37+43
CASE 139:
101+107+109+11+11+113+13+13+17+17+19+19+2+23
CASE 140:
No Solution.
CASE 141:
No Solution.
CASE 142:
107+11+11+127+127+13+13+2+3+31+41
CASE 143:
101+103+11+17+7+7
CASE 144:
17+2+23+29+29+3+3+5+53
CASE 145:
101+103+103+19+37
CASE 146:
11+13+13+17+17+19+19+2+23+23+29+31
CASE 147:
101+103+103+107+107+11+11+13+2
CASE 148:
101+101+103+103+107+109+109+11+11+113+113+13+2
CASE 149:
163+2+283+293
CASE 150:
101+3+3+5+67+7
CASE 151:
No Solution.
CASE 152:
103+103+107+107+109+11+11+2
CASE 153:
163+269+281
CASE 154:
101+11+3+3+5+7
CASE 155:
No Solution.
CASE 156:
229+229+257+283
CASE 157:
No Solution.
CASE 158:
101+103+103+107+139+2
CASE 159:
179+293+293+97
CASE 160:
101+103+107+107+109+11+11+13+13+227
CASE 161:
101+131+23+3+47
CASE 162:
No Solution.
CASE 163:
13+2+3+3+43+5+5+7+7
CASE 164:
163+277+277
CASE 165:
101+103+103+107+107+11+11+2
CASE 166:
101+103+107+107+11+139+223
CASE 167:
No Solution.
CASE 168:
101+167+191+2+241+277
CASE 169:
No Solution.
CASE 170:
101+101+107+107+109+11+11+13+13+17+17+19
CASE 171:
No Solution.
CASE 172:
11+11+17+2+3+3+31+5+5+7+7
CASE 173:
103+11+13+13+149+2
CASE 174:
101+103+167+227
CASE 175:
227+271
CASE 176:
167+293
CASE 177:
101+103+103+107+109+197
CASE 178:
11+11+113+13+13+17+17+19+19+23+37+37
CASE 179:
107+11+11+13+17+17+19+3+5+83
CASE 180:
101+101+11+11+13
CASE 181:
127+2
CASE 182:
227+97
CASE 183:
No Solution.
CASE 184:
2+281+293+293
CASE 185:
163+2+223+229+283
CASE 186:
17+17+19+19+2+23+5+53
CASE 187:
No Solution.
CASE 188:
103+103+107+107+11+11+13+13+17+17+19+19+23
CASE 189:
101+2+47

[Silverfox03]

Your output is really make me confused.
CASE 1:
11+11+113+113+13+13+17+17+19+19

my answer:
101+101+103+11+3+3+5+5+7+7

I think my answer is smaller than you.
Can you explain it?

[Silverfox03]

This my code. plz tell me what's wrong, or tell me the the lexicographically smallest expression really mean! thanks!!!

[cpp]
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdio.h>

#ifdef ONLINE_JUDGE
istream &fin=cin;
#else
ifstream fin("10419.in");
#endif

struct Sum//The structure of the sum expression
{
bool exist;
int result[14];
};

int Primes[62];//All the primes less than 300
char Spri[62][4];//The string format of prime
Sum Sums[14][1001];//The table of sum-expressions that generated by DP

void Num2Str(int num,char s[4])//Convert number into string
{
if (num>=100)
s[0]=num/100+48,s[1]=(num%100)/10+48,s[2]=num%10+48,s[3]=0;
else if (num>=10)
s[0]=num/10+48,s[1]=num%10+48,s[2]=0;
else
s[0]=num+48,s[1]=0;
}

void GetPrimes()//Get all the primes
{
int i,j,p;
bool Is[301];

for (i=3;i<301;i+=2)
Is=true;
for (i=0;i<62;i++)
Spri[0]=0;
Primes[0]=2;
strcpy(Spri[0],"2");
p=0;
for (i=3;i<301;i+=2)
if (Is)
{
p++;
Primes[p]=i;
Num2Str(i,Spri[p]);
for (j=2*i;j<301;j+=i)
Is[j]=false;
}
}

bool Use(int num,Sum s,int len)//Judge whether the prime can use
{
int appear=0,i;

if (s.exist)
{
for (i=0;i<len;i++)
if (s.result==num)
appear++;
if (appear>1)
return false;
if (appear&&num==0)
return false;
return true;
}
else
return false;
}

bool Compare(int re1[14],int re2[14],int len)//Compare two sum-expressions
{
int i,t;

for (i=0;i<len;i++)
{
t=strcmp(Spri[re1],Spri[re2]);
if (t>0)
return false;
else if (t<0)
return true;
}
}

void Generate()//Generate the table of sum-expressions
{
int i,j,k,l,a;

for (i=0;i<14;i++)
for (j=0;j<1001;j++)
Sums[j].exist=false;//Clear the table
for (i=0;i<62;i++)
{
a=Primes;
Sums[0][a].exist=true,Sums[0][a].result[0]=i;
}//Only primes can be the sum of one prime
for (i=1;i<14;i++)
for (j=2;j<1001;j++)
{
k=0;
while (j-Primes[k]>1&&k<62)//Only test the primes that smaller than the sum
{
a=Primes[k];
if (Use(k,Sums[i-1][j-a],i))
if (!(Sums[j].exist&&Compare(Sums[j].result,Sums[i-1][j-a].result,i)))
{//Judge whether the sum-expression now is smaller than the last one
for (l=0;l<i;l++)
Sums[i][j].result[l]=Sums[i-1][j-a].result[l];
Sums[i][j].result[i]=k;
Sums[i][j].exist=true;
}
k++;
}
}
}

void Print(int result[14],int len)//Output the answer
{
int i;

printf("%s",Spri[result[0]]);
for (i=1;i<len;i++)
printf("+%s",Spri[result[i]]);
printf("\n");
}

int main()
{
int n,t,c=1;

GetPrimes();
Generate();

fin>>n>>t;
while (n||t)
{
printf("CASE %d: %d %d\n",c,n,t);
if (t&&Sums[t-1][n].exist)
Print(Sums[t-1][n].result,t);
else
printf("No Solution.\n");
c++;
fin>>n>>t;
}

return 0;
}
[/cpp]

[little joey]

Alu's output is wrong, your output is correct. In fact most of Alu's output is wrong.

Code: Select all

CASE 1:
101+101+103+11+3+3+5+5+7+7
CASE 2:
101+101+103+103+107+107+109+109+113+19
CASE 3:
101+101+103+103+107+107+23
CASE 4:
101+101+103+103+107+11+11+13+23+5
CASE 5:
No Solution.
CASE 6:
101+101+103+103+107+107+151+223
CASE 7:
101+101+103+263
CASE 8:
101+101+103+103+11+11+13+17+7+7
CASE 9:
101+101+103+11+2+89
CASE 10:
101+101+103+11+11+13+13+17+17+2+23+29
CASE 11:
No Solution.
CASE 12:
101+11+11+13+47
CASE 13:
11+11+13+13+17+17+19+19+2+23+23+3+5+7
CASE 14:
101+101+3+3+7+7
CASE 15:
No Solution.
CASE 16:
No Solution.
CASE 17:
101+101+103+103+107+107+109+109+11+11+17+2+97
CASE 18:
101+101+103+149+277
CASE 19:
107+2+281+293+293
CASE 20:
101+101+103+103+11+11+13+13+17+17+19+37
CASE 21:
101+101+103+103+11+13+2+37
CASE 22:
101+101+103+103+11+11+2+3+3
CASE 23:
No Solution.
CASE 24:
101+101+103+103+107+107+109+11+2
CASE 25:
No Solution.
CASE 26:
101+101+103+11+11+13+13+2+23+29
CASE 27:
101+101+103+103+109+2+251
CASE 28:
11+11+13+13+2+43
CASE 29:
101+101+103+11+11+3+5
CASE 30:
167+2+293+293
CASE 31:
101+101+103+103+107+11+11+13+13+2+5+7+7
CASE 32:
101+101+103+109+2+241
CASE 33:
101+103+173
CASE 34:
101+101+103+103+107+11+11+13+2
CASE 35:
11+11+13+13+17+17+19+19+2+23+23+3+3
CASE 36:
11+11+2+29
CASE 37:
101+101+11+11+13+17+29
CASE 38:
No Solution.
CASE 39:
101+101+103+103+107+11+2+97
CASE 40:
101+101+103+103+11+11+17+7
CASE 41:
101+101+103+103+107+107+109+11+11+13+23+29
CASE 42:
101+101+103+103+107+107+3+3+5+5
CASE 43:
11+11+79
CASE 44:
101+11+2+41
CASE 45:
127+281+293+293
CASE 46:
271+271
CASE 47:
No Solution.
CASE 48:
101+101+103+103+127+127
CASE 49:
11+11+13+13+17+17+2+23+5+7
CASE 50:
101+101+103+3+3+5+7
CASE 51:
No Solution.
CASE 52:
101+101+103+103+107+107+11+11+13+13+17+2+37
CASE 53:
2+241+293
CASE 54:
No Solution.
CASE 55:
No Solution.
CASE 56:
101+101+107+149
CASE 57:
101+101+103+11+11+13+19+19+3+3+5+5+7+7
CASE 58:
No Solution.
CASE 59:
No Solution.
CASE 60:
No Solution.
CASE 61:
101+101+109+139+2
CASE 62:
101+11+2+3+3+5+5+7+7
CASE 63:
101+101+103+103+107+107+11+37
CASE 64:
101+101+103+11+11+2+3+5+5+7+7
CASE 65:
101+101+11+11+13+13+17+17+19+2
CASE 66:
No Solution.
CASE 67:
101+101+11+11+13+13+17+2+37
CASE 68:
101+101+103+103+107+107+109+3+3+7
CASE 69:
11+11+13+13+17+2+3+3+5+5
CASE 70:
101+11+11+13+13+17+19+43
CASE 71:
101+101+103+103+11+11+2+3+5+5+7+7
CASE 72:
101+101+103+103+127+67
CASE 73:
No Solution.
CASE 74:
101+101+11+11+13+13+17+17+2+23+23
CASE 75:
101+101+103+2+223+277
CASE 76:
101+197+2+293+293
CASE 77:
233+269
CASE 78:
13+2+79
CASE 79:
No Solution.
CASE 80:
No Solution.
CASE 81:
101+101+11+11+13+13+17+17+3+3+5+5
CASE 82:
101+101+103+103+107+11+11+7+7
CASE 83:
11+11+13+13+17+17+2+3+3+7
CASE 84:
281+293+293
CASE 85:
101+11+11+13+3+3
CASE 86:
No Solution.
CASE 87:
101+101+103+151+2+277
CASE 88:
No Solution.
CASE 89:
101+11+11+13+13+7+7
CASE 90:
101+101+11+11+17+47
CASE 91:
No Solution.
CASE 92:
101+101+103+103+107+107+109+109+11+113+2+31
CASE 93:
No Solution.
CASE 94:
101+101+103+103+2+227+269
CASE 95:
101+101+103+103+107+107+109+43
CASE 96:
101+101+103+103+107+11+11+13+3
CASE 97:
No Solution.
CASE 98:
101+101+103+103+107+107+109+11+11+17+53
CASE 99:
No Solution.
CASE 100:
11+11+13+13+17+17+7+7
CASE 101:
101+101+11+11+13+13+17+3+7
CASE 102:
101+101+103+103+107+107+2+3
CASE 103:
11+11+13+13+17+19+43
CASE 104:
No Solution.
CASE 105:
101+101+103+103+2+223+277
CASE 106:
101+101+103+103+107+107+109+2+3+3+5+7+7
CASE 107:
11+11+13+13+17+19+19+2
CASE 108:
No Solution.
CASE 109:
No Solution.
CASE 110:
No Solution.
CASE 111:
101+101+11+11+13+13+17+2+23+5+7
CASE 112:
No Solution.
CASE 113:
101+11+11+13+13+17+17+19+19+23+3+7+7
CASE 114:
No Solution.
CASE 115:
No Solution.
CASE 116:
No Solution.
CASE 117:
101+101+103+103+107+107+109+11+11+13+17+59
CASE 118:
11+11+3+3+7+7
CASE 119:
101+101+227+271
CASE 120:
No Solution.
CASE 121:
101+101+103+103+227+269
CASE 122:
101+101+103+103+107+107+109+11+11+13+13+2+67
CASE 123:
No Solution.
CASE 124:
101+101+127+241
CASE 125:
101+101+103+103+107+107+11+281
CASE 126:
101+101+103+2+241
CASE 127:
101+101+103+11+13+2+79
CASE 128:
101+139+2+293

CASE 129:
101+109+199+2
CASE 130:
101+101+103+103+107+11+11+13+17+2+59
CASE 131:
101+101+103+103+11+11+13+13
CASE 132:
101+149+277+293
CASE 133:
101+101+103+103+107+11+11+13+13+17+2+3+5+7
CASE 134:
101+101+269+283
CASE 135:
No Solution.
CASE 136:
No Solution.
CASE 137:
101+11+11+13+13+17+17+2+29+3+7
CASE 138:
101+101+103+103+3+3+7+7
CASE 139:
101+101+103+103+107+11+11+13+2+3+3+5+5+7
CASE 140:
No Solution.
CASE 141:
No Solution.
CASE 142:
101+101+103+103+11+11+13+13+2+23+5
CASE 143:
101+101+11+11+17+5
CASE 144:
101+11+11+13+13+2+3+3+7
CASE 145:
101+101+103+11+47
CASE 146:
101+11+11+13+13+17+17+19+2+3+3+7
CASE 147:
101+101+103+103+107+11+11+19+2
CASE 148:
101+101+103+103+107+107+109+109+11+11+113+19+2
CASE 149:
163+2+283+293
CASE 150:
101+11+11+13+13+37
CASE 151:
No Solution.
CASE 152:
101+101+103+103+107+13+2+23
CASE 153:
127+293+293
CASE 154:
101+11+3+3+5+7
CASE 155:
No Solution.
CASE 156:
131+281+293+293
CASE 157:
No Solution.
CASE 158:
101+101+103+109+139+2
CASE 159:
101+191+277+293
CASE 160:
101+101+103+103+107+107+109+11+13+47
CASE 161:
101+101+11+13+79
CASE 162:
No Solution.
CASE 163:
11+11+13+13+19+2+5+7+7
CASE 164:
131+293+293
CASE 165:
101+101+103+103+107+11+17+2
CASE 166:
101+101+103+103+107+109+167
CASE 167:
No Solution.
CASE 168:
101+101+199+2+283+293
CASE 169:
No Solution.
CASE 170:
101+101+103+103+107+11+11+13+13+17+17+29
CASE 171:
No Solution.
CASE 172:
11+11+13+13+17+17+2+3+3+5+7
CASE 173:
101+101+11+17+2+59
CASE 174:
101+101+103+293
CASE 175:
227+271
CASE 176:
167+293
CASE 177:
101+101+103+103+113+199
CASE 178:
101+101+11+11+13+13+17+17+19+19+3+5
CASE 179:
101+101+11+11+13+13+17+5+7+7
CASE 180:
101+101+11+11+13
CASE 181:
127+2
CASE 182:
101+223
CASE 183:
No Solution.
CASE 184:
2+281+293+293
CASE 185:
101+2+211+293+293
CASE 186:
101+11+11+13+2+3+7+7
CASE 187:
No Solution.
CASE 188:
101+101+103+103+11+11+13+13+17+17+19+23+31
CASE 189:
101+2+47

[alu_mathics]

sorry i haven't judge the outputs carefully.But this has been genrated from my A.C. solution.Long time ago Adrian also pointed out the fact.May
be it is becoz of the borland compiler i used.Strange but true.I should try with my Vcc compiler.
Silverfox03 your output is correct.

[alu_mathics]

I have check the above input using Vcc and they were the same as little joy.
Thanks little joy for pointing out the fact.
Hope the following are correct.

Code: Select all

52 6
349 2
818 12
63 13
983 8
356 9
419 12
167 6
291 10
165 1
181 3
808 6
142 10
878 12
750 13
373 13
175 8
981 2
70 10
8 4
392 11
835 3
198 3
74 2
387 9
885 3
822 2
424 4
530 11
704 7
13 10
739 14
713 5
476 10
661 1
335 1
81 6
280 13
662 1
16 4
288 8
286 1
149 4
163 5
255 13
412 7
602 10
465 7
599 3
756 9
887 11
363 12
614 9
297 14
820 6
707 1
50 13
71 4
78 12
657 8
181 14
109 8
91 5
234 6
103 6
220 7
113 8
163 10
262 6
838 1
20 12
478 5
679 1
320 14
481 1
223 8
181 13
68 3
440 1
335 12
661 14
889 6
391 14
886 8
313 12
342 11
240 10
635 6
361 14
73 7
966 7
600 14
539 5
431 1
578 4
934 5
626 10
788 1
959 14
454 4
479 10
1 14
60 14
853 5
441 3
175 7
504 13
644 5
225 6
935 11
788 13
779 14
572 2
460 8
269 5
750 14
126 11
212 10
980 1
245 4
972 6
525 4
786 5
428 4
841 3
834 12
62 7
257 10
361 12
610 10
98 3
208 2
243 6
823 5
745 13
570 11
179 13
795 10
890 9
504 14
221 14
648 3
615 3
903 6
917 12
69 2
380 10
100 14
754 3
622 13
97 9
332 10
865 7
343 3
712 4
482 10
860 9
851 1
516 13
455 5
919 11
720 14
176 5
849 10
665 4
771 11
171 2
509 13
117 2
835 14
273 4
916 2
479 7
491 9
756 1
862 11
599 7
807 3
732 13
873 4
476 12
737 12
18 12
547 11
514 14
300 3
827 4
722 4

Output

Code: Select all

CASE 1:
11+11+13+3+7+7
CASE 2:
No Solution.
CASE 3:
101+101+103+103+107+107+109+11+11+13+23+29
CASE 4:
No Solution.
CASE 5:
101+101+103+103+107+173+2+293
CASE 6:
101+101+103+11+11+13+2+7+7
CASE 7:
101+101+103+11+11+13+13+17+17+2+23+7
CASE 8:
101+11+11+13+2+29
CASE 9:
101+101+11+11+13+13+17+17+2+5
CASE 10:
No Solution.
CASE 11:
101+13+67
CASE 12:
101+101+103+103+107+293
CASE 13:
11+11+13+13+17+17+19+29+5+7
CASE 14:
101+101+103+103+107+107+109+109+11+11+13+3
CASE 15:
101+101+103+103+107+107+11+11+13+13+17+2+61
CASE 16:
101+101+11+11+13+13+17+17+19+19+23+23+5
CASE 17:
101+11+11+13+13+17+2+7
CASE 18:
No Solution.
CASE 19:
No Solution.
CASE 20:
No Solution.
CASE 21:
101+101+103+11+11+13+13+17+17+2+3
CASE 22:
269+283+283
CASE 23:
107+2+89
CASE 24:
13+61
CASE 25:
101+101+103+11+11+13+13+17+17
CASE 26:
No Solution.
CASE 27:
No Solution.
CASE 28:
101+101+109+113
CASE 29:
101+101+103+103+11+11+13+13+19+2+53
CASE 30:
101+101+103+103+11+2+283
CASE 31:
No Solution.
CASE 32:
101+101+103+103+107+107+11+11+13+13+17+19+2+31
CASE 33:
101+101+103+127+281
CASE 34:
101+101+103+103+11+11+13+13+17+3
CASE 35:
No Solution.
CASE 36:
No Solution.
CASE 37:
11+11+13+13+2+31
CASE 38:
101+11+11+13+13+17+17+19+19+2+23+29+5
CASE 39:
No Solution.
CASE 40:
3+3+5+5
CASE 41:
101+101+11+11+13+13+19+19
CASE 42:
No Solution.
CASE 43:
101+17+2+29
CASE 44:
101+11+11+17+23
CASE 45:
101+11+11+13+13+17+17+19+19+23+3+3+5
CASE 46:
101+101+103+11+11+2+83
CASE 47:
101+101+103+103+107+11+11+13+23+29
CASE 48:
101+101+103+103+11+17+29
CASE 49:
101+227+271
CASE 50:
101+101+103+103+107+107+109+2+23
CASE 51:
101+101+103+103+107+107+109+109+11+13+23
CASE 52:
101+101+103+13+13+2+3+3+5+5+7+7
CASE 53:
101+101+103+103+107+11+13+2+73
CASE 54:
101+11+11+13+13+17+17+19+19+2+23+3+41+7
CASE 55:
101+101+103+103+131+281
CASE 56:
No Solution.
CASE 57:
No Solution.
CASE 58:
11+11+2+47
CASE 59:
No Solution.
CASE 60:
101+101+103+103+107+109+2+31
CASE 61:
11+11+13+13+17+17+19+19+2+23+23+3+3+7
CASE 62:
11+11+13+13+17+19+2+23
CASE 63:
11+11+13+13+43
CASE 64:
101+101+11+11+3+7
CASE 65:
11+11+13+13+2+53
CASE 66:
101+101+2+3+3+5+5
CASE 67:
11+11+13+13+17+17+2+29
CASE 68:
101+11+11+13+2+3+3+5+7+7
CASE 69:
101+101+11+11+19+19
CASE 70:
No Solution.
CASE 71:
No Solution.
CASE 72:
101+101+107+167+2
CASE 73:
No Solution.
CASE 74:
101+101+11+11+13+13+17+23+3+3+5+5+7+7
CASE 75:
No Solution.
CASE 76:
101+11+11+13+13+19+2+53
CASE 77:
11+11+13+13+17+17+19+19+23+23+3+5+7
CASE 78:
13+2+53
CASE 79:
No Solution.
CASE 80:
101+101+11+11+13+13+17+17+19+2+23+7
CASE 81:
101+101+103+103+107+11+11+13+13+17+17+19+2+43
CASE 82:
101+101+109+2+283+293
CASE 83:
101+101+103+11+11+13+19+2+3+3+5+5+7+7
CASE 84:
101+101+103+103+107+107+113+151
CASE 85:
101+101+11+11+13+13+17+17+19+2+3+5
CASE 86:
101+101+11+11+13+13+17+17+19+2+37
CASE 87:
101+11+11+13+13+17+17+19+31+7
CASE 88:
101+101+103+131+197+2
CASE 89:
101+101+11+11+13+13+17+17+19+19+2+23+7+7
CASE 90:
11+11+13+13+17+3+5
CASE 91:
101+101+103+103+2+263+293
CASE 92:
101+101+103+103+107+11+11+13+13+17+3+3+7+7
CASE 93:
101+101+103+103+131
CASE 94:
No Solution.
CASE 95:
101+101+107+269
CASE 96:
101+2+257+281+293
CASE 97:
101+101+103+103+107+11+11+13+17+59
CASE 98:
No Solution.
CASE 99:
101+101+103+103+107+107+109+109+11+11+13+2+23+59
CASE 100:
101+101+103+149
CASE 101:
101+101+103+103+11+11+13+17+17+2
CASE 102:
No Solution.
CASE 103:
No Solution.
CASE 104:
101+101+103+271+277
CASE 105:
101+101+239
CASE 106:
101+11+11+13+13+19+7
CASE 107:
101+101+103+103+11+11+13+13+17+17+2+5+7
CASE 108:
101+101+157+2+283
CASE 109:
101+101+11+2+3+7
CASE 110:
101+101+103+103+107+107+109+109+11+11+73
CASE 111:
101+101+103+103+107+107+109+11+11+13+13+2+7
CASE 112:
101+101+103+103+107+107+109+11+11+13+2+3+3+5
CASE 113:
No Solution.
CASE 114:
101+101+103+103+11+11+13+17
CASE 115:
101+101+11+13+43
CASE 116:
101+101+103+103+107+107+11+11+13+13+17+17+23+23
CASE 117:
11+11+13+13+17+17+2+23+5+7+7
CASE 118:
101+11+11+13+13+17+17+19+3+7
CASE 119:
No Solution.
CASE 120:
101+101+2+41
CASE 121:
101+101+103+103+271+293
CASE 122:
101+139+2+283
CASE 123:
101+107+2+283+293
CASE 124:
101+101+113+113
CASE 125:
271+277+293
CASE 126:
101+101+103+103+107+107+109+11+11+13+31+37
CASE 127:
11+11+13+13+2+5+7
CASE 128:
101+101+11+11+13+2+3+3+5+7
CASE 129:
101+101+103+11+13+2+3+3+5+5+7+7
CASE 130:
101+101+103+103+107+11+11+13+13+47
CASE 131:
13+2+83
CASE 132:
101+107
CASE 133:
101+101+11+11+17+2
CASE 134:
101+101+103+241+277
CASE 135:
101+101+103+103+107+107+11+11+13+13+17+17+41
CASE 136:
101+101+103+103+107+11+11+13+13+2+5
CASE 137:
11+11+13+13+17+17+19+19+23+23+3+3+7
CASE 138:
101+101+103+103+107+107+109+19+2+43
CASE 139:
101+101+103+103+107+107+109+157+2
CASE 140:
101+101+103+103+11+11+13+13+23+3+3+5+7+7
CASE 141:
101+11+11+13+13+17+2+23+3+3+5+5+7+7
CASE 142:
No Solution.
CASE 143:
101+233+281
CASE 144:
101+101+113+2+293+293
CASE 145:
101+101+103+103+107+107+109+109+11+11+2+53
CASE 146:
2+67
CASE 147:
101+101+103+11+11+13+13+17+3+7
CASE 148:
No Solution.
CASE 149:
No Solution.
CASE 150:
101+101+103+103+107+11+11+13+13+17+17+2+23
CASE 151:
11+11+13+13+17+17+3+5+7
CASE 152:
101+101+11+11+13+13+17+17+19+29
CASE 153:
101+101+103+103+107+109+241
CASE 154:
101+103+139
CASE 155:
101+101+227+283
CASE 156:
101+101+103+103+11+11+13+13+19+7
CASE 157:
101+101+103+103+107+107+109+127+2
CASE 158:
No Solution.
CASE 159:
101+101+103+103+11+11+13+13+17+17+19+2+5
CASE 160:
101+101+103+103+47
CASE 161:
101+101+103+103+107+107+109+109+11+31+37
CASE 162:
101+101+103+103+107+107+11+11+13+13+17+19+7+7
CASE 163:
101+11+19+2+43
CASE 164:
101+101+103+103+107+107+109+109+2+7
CASE 165:
101+2+269+293
CASE 166:
101+101+103+103+107+107+109+11+11+13+5
CASE 167:
No Solution.
CASE 168:
101+101+103+103+11+11+13+13+17+17+5+7+7
CASE 169:
No Solution.
CASE 170:
101+101+103+103+107+107+109+11+11+13+13+17+2+37
CASE 171:
101+103+2+67
CASE 172:
No Solution.
CASE 173:
101+101+103+103+11+13+47
CASE 174:
101+101+103+103+11+11+13+17+31
CASE 175:
No Solution.
CASE 176:
101+101+103+103+107+107+109+109+13+2+7
CASE 177:
101+101+103+103+107+11+73
CASE 178:
233+281+293
CASE 179:
101+101+103+103+107+107+11+11+13+13+17+2+43
CASE 180:
No Solution.
CASE 181:
101+101+103+103+11+11+13+13+3+3+7+7
CASE 182:
101+101+103+103+107+107+11+11+13+17+2+61
CASE 183:
No Solution.
CASE 184:
101+101+103+103+109+3+3+5+5+7+7
CASE 185:
101+101+103+103+11+11+13+13+17+17+5+5+7+7
CASE 186:
101+197+2
CASE 187:
2+239+293+293
CASE 188:
101+101+227+293

One more thing still the output generated using the borland compiler does not match with the above.

[Silverfox03]

alu_mathics:
Your last I/O is correct, and the last I/O let me find the last mistake in my program! After almost two weeks work, this problem is solved finally.
Thank to all that post reply to this topic!

[asif_rahman0]

Here is my code.Plz tell me why I got TLE.
#include<stdio.h>
#include<math.h>

long prime[1000],n,k,out[1000],sum,comp,present[1000];

long is_prime( long n1 )
{
long x,i;
x = sqrt(n1);
for( i = 2; i <= x; i++ )
if( n1 % i == 0 )
return 0;
return 1;
}
void calculate_number( long i )
{
i--;
sum = 0;
while( i >= 0 )
{
sum += out;
i--;
}
}
void recure( long x, long len , long pi)
{
long i;
calculate_number(len);
if( sum > n )
{
present[pi]--;
return;
}
if( len == k )
{
if( sum == n )
comp = 1;
present[pi]--;
return;
}
for(i = 1; prime <= n && comp == 0 && prime < 300 ; i++ )
{
if( present > 2 )
continue;
present++;
out[len] = prime;
recure(prime,len+1,i);
}
}
void main( void )
{
long i,j,cas,l;
prime[0] = 2;

for( i = 3, j = 1; i < 300; i += 2 )
{
if( is_prime(i) )
prime[j++] = i;

}
prime[j] = 100000;
cas = 1;
scanf("%ld%ld",&n,&k);
while( n )
{
comp = 0;
for( i = 0; prime <= n && comp == 0 ;i++ )
{
for( l = 0; l < j; l++ )
present[l] = 1;
present[0] = 3;
out[0] = prime;
present++;
recure(prime[i],1,i);
}
printf("CASE %ld:\n",cas);
if( comp )
{
for( i = 0; i < k-1 ; i++ )
printf("%ld+",out[i]);
printf("%ld\n",out[i]);
}
else
printf("No Solution.\n");
cas++;
scanf("%ld%ld",&n,&k);

}

}

[..]

PLEASE

1. Post at the correct Volume

2. Use the "search" function before posting, all the answers you needed are already included in the old discussion thread. Just use the problem id to search.

[Mohammad Mahmudur Rahman]

Well, though I can't find any logical error in my program & it passes all the test data found in the board as well created by myself; this problem took a whole night of work from me with the reward of repeated WAs. Someone please figure out what's wrong here.

Code: Select all

//code deleted

[little joey]

Try

Code: Select all

43 7
157 9
0 0

Your program:

Code: Select all

CASE 1:
No Solution.
CASE 2:
11+11+13+13+17+17+19+19+37

My program:

Code: Select all

CASE 1:
13+3+3+5+5+7+7
CASE 2:
101+13+13+3+3+5+5+7+7

[Mohammad Mahmudur Rahman]

Thanks Little Joey, I made a terrible mistake in the prunning part. I wonder how my earlier program passed so many test cases. However, as I corrected the program, it got really interesting (or irritating, I should say ). It began to recieve TLE again. But I tested the program with an input file containing all 14000 possible test cases & none seemed to stall or slow-down the program. What might be the case then? I am giving the modified source code. Hope you can help me.

Code: Select all

//code deleted

[little joey]

As far as I can tell, your program gives correct answers now, but is too slow, indeed.
You could try memoization to attain the necessary speedup: your function backtrack(int ind, int val, int start) gets called with the same parameters many times, but you only have to search each tree once. Something similar to your previous array reach, but I think you should use a three dimensional array instead and not clear it between cases.

[Mohammad Mahmudur Rahman]

Thanks a lot. Got the point at last.

[rezaeeEE]

my program passed all the testcases what exist in this thread.

Can any body help me?

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;
	//FILE * wt = fopen( "out.txt", "w+" );
	//while( scanf( "%d%d", &n, &t ),  n || t ){
	while( cin >> n >> t, n || t ){
		int can = solve( 0, t, n );
		//fprintf( wt, "CASE %d:\n", test++ ); 
		int first = 1;
		if( !can )
			//fprintf( wt, "No Solution.\n" );
			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 )
						//fprintf( wt, "+" );
						cout << '+';
					first = 0;
					//fprintf( wt, "%d", prime[tptr] );
					cout << prime[tptr];
				}
				tsum -= tp * prime[tptr];
				tptr++;
				tcnt -= tp;
			}
			//fprintf( wt, "\n" );
			cout << endl;
		}
		//fflush( wt );
	}
	return 0;
}

thanks.