fork download
copy 
  1. program luck;
  2. { constraints }
  3. const
  4.     MAXN = 200;
  5.     MAXC = 10000;
  6.     INF  = 4*MAXC;
  7.  
  8. { input data }
  9. var
  10.     N,C,i,j,k: longint;
  11.     M10, D10 : array[1..4] of longint;                      { powers of 10 to extract digits by mod or div }
  12.     L        : array[1..MAXN] of longint;                   { lucky numbers }
  13.     pfx      : array[1..MAXN] of array[1..MAXN] of longint; { how overlapping numbers are }
  14.     good     : array[1..MAXC] of array[1..MAXN] of longint; { good[k,i] = how short can k numbers starting from L[i] be }
  15.     mtch     : array[1..MAXC] of array[1..MAXN] of longint; { mtch[k,i] = next number to obtain good[k,i] }
  16.     best     : array[1..MAXC] of longint;                   { best[k]   = best start for k numbers }
  17.  
  18. begin
  19. {
  20.     uncomment the following lines if you want to read/write from files
  21.     assign(input,  'input.txt');  reset(input);
  22.     assign(output, 'output.txt'); rewrite(output);
  23. }
  24.  
  25.     readln(N, C);
  26.     for i:=1 to N do begin
  27.         read(L[i]);
  28.         good[1,i] := 4;  { L[i] has 4 digits }
  29.         mtch[1,i] := -1; { nothing after L[i] }
  30.     end;
  31.     readln();
  32.     best[1] := 1; { all equivalent for k=1 }
  33.     M10[1] := 10;
  34.     M10[2] := 100;
  35.     M10[3] := 1000;
  36.     M10[4] := 10000;
  37.     D10[1] := 1000;
  38.     D10[2] := 100;
  39.     D10[3] := 10;
  40.     D10[4] := 1;
  41.     for i:=1 to N do for j:=1 to N do begin
  42.         pfx[i,j] := 4; { no overlap }
  43.         for k:=1 to 3 do if L[i] mod M10[k] = L[j] div D10[k] then
  44.             pfx[i,j] := 4-k; { overlap found }
  45.     end;
  46.     for k:=2 to C-3 do begin
  47.         best[k] := 1;
  48.         for i:=1 to N do begin
  49.             good[k,i] := INF;
  50.             for j:=1 to N do if pfx[i,j] + good[k-1,j] < good[k,i] then begin
  51.                 good[k,i] := pfx[i,j] + good[k-1,j];
  52.                 mtch[k,i] := j; { use j after i }
  53.             end;
  54.             if good[k,i] < good[k,best[k]] then
  55.                 best[k] := i; { use i for k numbers }
  56.         end;
  57.         if good[k,best[k]] >= C then break; { no way to be within C digits for larger k }
  58.     end;
  59.     if good[k,best[k]] > C then k := k-1;
  60.     i := best[k]; { starting number }
  61.     for j:=1 to C-good[k,best[k]] do write(0); { padding digits to reach length C }
  62.     for k:=k downto 2 do begin
  63.         { write first digits of L[i] }
  64.         for j:=1 to pfx[i,mtch[k,i]] do
  65.             write((L[i] div D10[j]) mod 10);
  66.         i := mtch[k,i] { next number }
  67.     end;
  68.     writeln(L[i]);
  69. end.
  70.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
01
https://ideone.com/S5vT39
language:
Pascal (fpc 3.0.4)
created:
7 days 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!