INFOMAN брой 3

{
                            НАЙ-ГОЛЯМО ПОДЧИСЛО
                            -------------------

     Дадени са две числа - N и K, които могат да имат до 5000 цифри. Подчисло
 на едно число наричаме всяко число, което може да се получи от даденото чрез
 отстраняване на 0, 1 или повече цифри от него.  Да се намери такова подчисло
 на N, че то да е най-голямото възможно, което не надвишава K.
     РЕШЕНИЕ: Решението винаги има или [K] или [K]-1 цифри или ако N < K  - N
 цифри, където с [x] означаваме броя цифри на x. Нека съществува число, което
 може да се образува чрез обхождане на числото N отляво надясно и избирателно
 вземане на текущата цифра от него. Да предположим, че търсим число с k цифри,
 което трябва да е максимално и да е подчисло на N.Тогава можем да намерим то-
 ва число със следния линеен алгоритъм ([N]<=k):
   повтаряй
      1. вземи първата най-голяма от първите [N]-k+1 цифри на N.
         Нека тя е на позиция P
      2. k:=k-1
      3. премахни първите P цифри на N
   докато е вярно (k > 0)
 Идеята на този алгоритъм е да се взима винаги най-голямата възможна цифра,но
 като прави сметка винаги да останат май-малко k-1 цифри в края на N. Това га-
 рантира, че на всяка стъпка ще можем да продължим, т.е. че винаги ще получим
 подчисло на N с k цифри.
     Алгоритъмът за намиране на максимално подчисло на N ненадвишаващо K е ус-
 ложнен вариант на дадения по-горе. Да означим с k [K] и с n [N]. Тогава алго-
 ритъма ще търси последователно в N максималната цифра, която не превишава те-
 кущата цифра на K, като си прави сметка винаги да оставя k-1 цифри, за да мо-
 же да се получи максимално число. Когато при сканирането не се отркие текуща-
 та цифра на K, се търси следващата по-малка, но вече следващите k-1 цифри на
 K стават девятки, защото ако веднъж изберем от N цифра,  която е по-малка от
 текущата цифра на K, след това каквито и цифри да избираме,винаги ще получим
 число по-малко от K, а най-изгодно е да търсим цифри най-близки до 9, защото
 ще получим най-голямо число.  Трябва да предвидим, че никое число не може да
 започва с 0.  Ако алгоритъма е открил при сканирането цифра, която съвпада с
 текущата цифра на K, се преминава към следващата цифра на K,а сканирането на
 N започва от следващата цифра в N.  Възможно е на някой ход да няма продълже-
 ние - да няма цифра, по-малка от текущата цифра на K. Тогава програмата тряб-
 ва да се върне назад и да избере следващата по големина цифра на предния ход.
 Ясно че, че повторно връщане няма да има,защото след като се избере следваща-
 та по големина цифра,  следващите докрая цифри ще станат девятки и винаги ще
 има продължение. Ако цялото търсене на k-цифрено подчисло на N,ненадвишаващо
 K пропадне, просто правим числото K да представлява k-1 девятки и пускаме от-
 ново търсенето.  Този път то не може да пропадне освен ако k няма повече циф-
 ри от N. В този случай решението очевидно е числото N. Общата сложност на це-
 лия алгоритъм е малко по-голяма от линейна, но много по-малка от квадратна и
 зависи от дадените N и K.
}
{$M 65520,0,655360}

USES Crt;

CONST MaxCifri = 5000;

TYPE Cislo =  record
                 Len: integer;
                 c: array[1..MaxCifri] of byte;
              end;

VAR N,K,Rez: Cislo;


Procedure ReadCislo(var C:Cislo); { Read long number C from keyboard }
Var Key: char;
Begin
  C.Len:=0;
  repeat
    Key:=ReadKey;
    if (Key in['0'..'9']) then
      begin Write(Key); Inc(C.Len); C.c[C.Len]:=ord(Key)-48; end
    else
      if ((Key=#8)or(Key=#75)) and (C.Len>0) then
        begin Dec(C.Len); Write(#8' '#8); end;
  until Key = #13;
End;

Procedure ReadData;
Begin
  Write('N = '); ReadCislo(N); WriteLn;
  Write('K = '); ReadCislo(K); WriteLn; WriteLn;
End;

Procedure WriteCislo(var C: Cislo); { Write C and exit the program }
Var i: integer;
Begin
  if C.Len = 0 then Write('0');
  for i:= 1 to C.Len do
    Write(C.c[i]);
  WriteLn; Halt;
End;

Function FindDigitInN(Digit:byte;Poz,EndPoz:integer): integer;
Begin { Find the position of first "Digit" in N from Poz to EndPoz }
  for Poz:= Poz to EndPoz do
    if N.c[Poz] = Digit then
      begin FindDigitInN:=Poz; Exit; end;
  FindDigitInN:=0;
End;

Procedure Find(PozN,PozK:integer);
Var Poz: integer;
    i: byte;
Begin
  if PozK > K.Len then WriteCislo(Rez); { Solution found }

  Poz:= FindDigitInN(K.c[PozK], PozN, N.Len-K.Len+PozK);
  if Poz <> 0 then
    begin { If equal digit found }
      Inc(Rez.Len); Rez.C[Rez.Len]:=N.c[Poz];
      Find(Poz+1,PozK+1);
      Dec(Rez.Len);
    end;

  for Poz:= PozK+1 to K.Len do K.c[Poz]:=9; { Enable all digits from now on }

  for i:= K.c[PozK]-1 downto 0 do
    begin { Try with digits less than K[PozK] }
      if (i=0) and (Rez.Len=0) then Continue;
      Poz:= FindDigitInN(i, PozN, N.Len-K.Len+PozK);
      if Poz <> 0 then
        begin
          Inc(Rez.Len); Rez.C[Rez.Len]:=N.c[Poz];
          Find(Poz+1,PozK+1);
          Dec(Rez.Len);
        end;
    end;
End;

BEGIN
  ReadData;
  { Try to find result with K.Len digits if any }
  Rez.Len:=0;
  Find(1,1);
  { Set K to '999...' and find result with K.Len-1 digits }
  Dec(K.Len); K.c[1]:=9;
  Find(1,1);
  WriteCislo(N); { N < K }
END.