kimbits.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 47 行

{
ID:maigoak1
PROG:kimbits
}

program kimbits;
const
  maxn=31;
var
  fin,fout:text;
  s:array[0..maxn-1,0..maxn-1]of int64;
    {s[x,y] means the number of x-bit strings with at most y 1s}
  n,l,j,k:integer;
  i:int64;
begin
  assign(fin,'kimbits.in');
  reset(fin);
  readln(fin,n,l,i);
  close(fin);
  assign(fout,'kimbits.out');
  rewrite(fout);

  {Calculate the array s}
  s[0,0]:=1;
  for j:=1 to n-1 do begin
    s[j,0]:=1;
    for k:=1 to j-1 do
      s[j,k]:=s[j-1,k]+s[j-1,k-1];
    s[j,j]:=s[j-1,j-1]*2;
  end;

  {Find the string}
  for j:=n-1 downto 0 do begin
    if l>j then l:=j;
    if i>s[j,l] then begin
      write(fout,1);
      i:=i-s[j,l];
      dec(l);
    end
    else
      write(fout,0);
  end;

  writeln(fout);
  close(fout);
end.