VN_ZR_I - Số không (I)

Tác giả: RR

Ngôn ngữ: Pascal

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Pham Quang Vu
program VN_ZR_I;
const
  inp='';
  out='';
type
  mang=array[1..50] of longint;
var
  fi,fo:text;
  n,k,nbit:longint;
  bit:mang;
  c:array[0..40,0..40] of int64;
procedure openfile;
begin
  assign(fi,inp);reset(fi);
  assign(fo,out);rewrite(fo);
end;
procedure getbit(x:longint;var c:mang;var top:longint);
begin
  top:=0;
  while x>0 do
    begin
      inc(top);
      c[top]:= x and 1;
      x:=x shr 1;
    end;
end;
procedure init;
var
  i,j:longint;
begin
  for i:=0 to 34 do c[0,i]:=1;
  for i:=1 to 34 do
    begin
      c[i,i]:=1;
      for j:=i+1 to 34 do c[i,j]:=c[i,j-1]+c[i-1,j-1];
    end;
end;
procedure solve;
var
  count,i,j:longint;
  result:int64;
begin
  getbit(n,bit,nbit);
  result:=0;
  for i:=nbit-1 downto 1 do
    for j:=1 to i-1 do
      result:=result+c[j,i-1]*((j-1) div k+1);
  count:=0;
  for i:=nbit-1 downto 1 do
    if bit[i]=1 then
      begin
        for j:=0 to i-1 do
          result:=result+c[j,i-1]*((j+count) div k+1);
      end
    else inc(count);
  if count>=1 then result:=result+(count-1) div k+1;
  writeln(fo,result);
end;
procedure enter;
begin
  init;
  while not eof(fi) do
    begin
      readln(fi,n,k);
      if (n=0) and (k=0) then exit;
      solve;
    end;
end;
procedure closefile;
begin
  close(fi);
  close(fo);
end;
begin
  openfile;
  enter;
  closefile;
end.

Download