Dwarf Home

type arr=array[0..100] of integer;
var f,ok,p,t,k,i,j:longint;
    s:string;
    a:array[0..332] of arr;
    b,b1:arr;
    c:array[1..100] of integer;
begin
  fillchar(a,sizeof(a),0);
  a[0,0]:=1;
  a[0,1]:=1;
  for i:=1 to 332 do begin
    p:=0;
    a[i,0]:=a[i-1,0];
    for j:=1 to a[i-1,0] do begin
      t:=a[i-1,j]*2;
      inc(a[i,j],t mod 10);
      inc(a[i,j],p);
      p:=t div 10;
    end;
    if p<>0 then begin
      inc(a[i,0]);
      a[i,a[i,0]]:=p;
    end;
    c[a[i,0]]:=i;
  end;
  readln(s);
  b[0]:=length(s);
  for i:=1 to b[0] do val(s[i],b[b[0]-i+1],ok);
  for i:=c[b[0]] downto 1 do begin
    f:=0;
    for j:=b[0] downto 1 do
      if b[j]>a[i,j]
        then begin
               f:=1;
               break;
             end
        else
          if b[j]=a[i,j]
            then continue
            else begin
                   f:=2;
                   break;
                 end;
    case f of
      1   :begin
             for k:=1 to j do begin
               if b[k]<0
                 then begin
                        dec(b[k+1]);
                        inc(b[k],10);
                      end;
               b1[k]:=b[k]-a[i,k];
               if b1[k]<0
                 then begin
                        inc(b1[k],10);
                        dec(b[k+1]);
                      end;
             end;
             b1[0]:=j;
             if b1[j]=0 then dec(b1[0]);
             str(i,s);
             fillchar(b,sizeof(b),0);
             b[0]:=length(s);
             t:=0;
             for j:=b[0] downto 1 do begin
               val(s[j],b[b[0]-j+1],ok);
               inc(b1[j],b[j]);
               if b1[j]>10
                 then begin
                        inc(b1[j+1]);
                        dec(b1[j],10);
                      end
             end;
             if b1[b1[0]+1]<>0 then inc(b1[0]);
             for j:=b1[0] downto 1 do write(b1[j]);
             writeln;
             halt;
           end;
      0   :begin
             writeln(s);
             halt;
           end;
      end;
  end;
end.