fork(1) download
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<cstring>
  7. #include<map>
  8. #include<set>
  9. #include<stack>
  10. #include<queue>
  11. #include<string>
  12. #include<iterator>
  13. #include<string>
  14. #include<sstream>
  15. #include<cassert>
  16. #include<ctime>
  17.  
  18. #define MP make_pair
  19. #define PII pair<int,int>
  20. #define PB push_back
  21. #define X first
  22. #define Y second
  23. #define oo 2000000000
  24. #define MOD 1000000007
  25. #define LL long long int
  26.  
  27. using namespace std;
  28. int N;
  29. char tmp[22];
  30. vector<string> array;
  31. int L[22];
  32. int dp[502];
  33. int label[22][22];
  34. PII val[502];
  35. string ds[502];
  36.  
  37.  
  38. int total_l;
  39.  
  40. bool isPrefix(int id1,int id2){
  41. PII p1=val[id1];
  42. PII p2=val[id2];
  43. if((L[p1.X]-p1.Y) > (L[p2.X]-p2.Y) ) return false;
  44. for(int i=0;i<L[p1.X]-p1.Y;i++){
  45. if(array[p1.X][i+p1.Y] != array[p2.X][i+p2.Y]) return false;
  46. }
  47. return true;
  48. }
  49.  
  50. int check(int id){
  51. PII lb = val[id];
  52. int &r = dp[id];
  53. int tp;
  54. if(r != -1 ) return r;
  55. r = oo;
  56. if(!lb.Y){
  57. for(int i=0;i<N;i++){
  58. if(i==lb.X) continue;
  59. if(isPrefix(label[i][0],label[lb.X][0])){
  60. tp = L[i]+check( label[lb.X][L[i]] );
  61. if(tp >= oo) continue;
  62. if(r > tp ) r = tp , ds[id] = array[i] + ds[label[lb.X][L[i]]];
  63. else if(r == tp) ds[id] = min(ds[id],array[i] + ds[label[lb.X][L[i]]]);
  64.  
  65. }
  66. else if(isPrefix(label[lb.X][0],label[i][0])){
  67. tp = L[lb.X] + check( label[i][L[lb.X]] );
  68. if(tp >= oo) continue;
  69. if(r > tp) r = tp , ds[id] = array[lb.X] + ds[label[i][L[lb.X]]];
  70. else if(r == tp) ds[id] = min(ds[id],array[lb.X]+ds[label[i][L[lb.X]]]);
  71. }
  72. }
  73. return r;
  74. }
  75. for(int i=0;i<N;i++){
  76. if(isPrefix(label[i][0],id)){
  77. tp = L[i]+check( label[lb.X][lb.Y+L[i]] );
  78. if(tp >= oo) continue;
  79. if(r > tp) r = tp , ds[id] = array[i] + ds[label[lb.X][lb.Y+L[i]]];
  80. else if(r == tp) ds[id] = min(ds[id] , array[i] + ds[label[lb.X][lb.Y+L[i]]]);
  81. }
  82. else if(isPrefix(id,label[i][0])){
  83. tp = L[lb.X]-lb.Y+check( label[i][L[lb.X]-lb.Y] );
  84. if(tp >= oo) continue;
  85. if(r > tp) r = tp , ds[id] = array[lb.X].substr(lb.Y)+ds[label[i][L[lb.X]-lb.Y]];
  86. else if(r == tp) ds[id] = min(ds[id] , array[lb.X].substr(lb.Y)+ds[label[i][L[lb.X]-lb.Y]] );
  87. }
  88. }
  89. return r;
  90. }
  91.  
  92. int main(){
  93. //freopen("input.txt","r",stdin);
  94. int T = 1;
  95. while(scanf("%d",&N),N){
  96. for(int i=0;i<N;i++){
  97. scanf("%s",tmp);
  98. array.PB(string(tmp));
  99. }
  100. sort(array.begin(),array.end());
  101. for(int i=0;i<N;i++)
  102. L[i]=array[i].length();
  103. total_l=0;
  104. for(int i=0;i<N;i++)
  105. for(int j=0;j<L[i];j++){
  106. label[i][j] = ++total_l , val[total_l] = MP(i,j);
  107. }
  108. ++total_l;
  109. for(int i=0;i<N;i++)
  110. label[i][L[i]] = total_l;
  111. for(int i=0;i<=total_l;i++)
  112. dp[i]=-1 , ds[i] = string("");
  113. dp[total_l]=0;
  114. int ans=oo;
  115. string ss;
  116. for(int i=1;i<N;i++){
  117. int tp = check(label[i][0]);
  118. if(tp == oo) continue;
  119. if(tp < ans) ans = tp ,ss = ds[label[i][0]];
  120. else if(tp == ans) ss = min(ss , ds[label[i][0]]);
  121. }
  122. assert(ans != oo);
  123. if(ans>1)
  124. printf("Code %d: %d bits\n",T,ans);
  125. else
  126. printf("Code %d: %d bit\n",T,ans);
  127. for(unsigned int i=0;i<ss.length();i++){
  128. putchar(ss[i]);
  129. if(i%20==19 || 1+i==ss.length()) puts("");
  130. }
  131. puts("");
  132. ++T;
  133. array.clear();
  134. }
  135. return 0;
  136. }
Success #stdin #stdout 0s 3052KB
stdin
3
0
01
10
5
0110
00
111
001100
110
5
1
001
0001
00000000000000000001
10000000000000000000
0
stdout
Code 1: 3 bits
010

Code 2: 9 bits
001100110

Code 3: 21 bits
10000000000000000000
1