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.     for i:=1 to N do write (good[1][i]); end.
  33.     best[1] := 1; { all equivalent for k=1 }
  34.     M10[1] := 10;
  35.     M10[2] := 100;
  36.     M10[3] := 1000;
  37.     M10[4] := 10000;
  38.     D10[1] := 1000;
  39.     D10[2] := 100;
  40.     D10[3] := 10;
  41.     D10[4] := 1;
  42.     for i:=1 to N do for j:=1 to N do begin
  43.         pfx[i,j] := 4; { no overlap }
  44.         for k:=1 to 3 do if L[i] mod M10[k] = L[j] div D10[k] then
  45.             pfx[i,j] := 4-k; { overlap found }
  46.     end;
  47.     for k:=2 to C-3 do begin
  48.         best[k] := 1;
  49.         for i:=1 to N do begin
  50.             good[k,i] := INF;
  51.             for j:=1 to N do if pfx[i,j] + good[k-1,j] < good[k,i] then begin
  52.                 good[k,i] := pfx[i,j] + good[k-1,j];
  53.                 mtch[k,i] := j; { use j after i }
  54.             end;
  55.             if good[k,i] < good[k,best[k]] then
  56.                 best[k] := i; { use i for k numbers }
  57.         end;
  58.         if good[k,best[k]] >= C then break; { no way to be within C digits for larger k }
  59.     end;
  60.     if good[k,best[k]] > C then k := k-1;
  61.     i := best[k]; { starting number }
  62.     for j:=1 to C-good[k,best[k]] do write(0); { padding digits to reach length C }
  63.     for k:=k downto 2 do begin
  64.         { write first digits of L[i] }
  65.         for j:=1 to pfx[i,mtch[k,i]] do
  66.             write((L[i] div D10[j]) mod 10);
  67.         i := mtch[k,i] { next number }
  68.     end;
  69.     writeln(L[i]);
  70. end.
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
2 9
1010 1031
stdout
copy 
44
https://ideone.com/fDNjDb
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!