fork(1) download
copy 
  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
comments (?)
stdin
copy 
3
0
01
10
5
0110
00
111
001100
110
5
1
001
0001
00000000000000000001
10000000000000000000
0
stdout
copy 
Code 1: 3 bits
010

Code 2: 9 bits
001100110

Code 3: 21 bits
10000000000000000000
1
https://ideone.com/DAiXA1
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!