Перейти к содержимому


Публикации kodosov

1 публикаций создано kodosov (учитываются публикации только с 30-марта 23)


#297 тесты Временной ключ Район 2008

Отправлено от kodosov в 23 мая 2013 - 16:41 in Флудилка

var wrem,ost:array[1..20,1..300000] of int64;
f:array[1..300000] of int64;
n,l,r,i,ans,k:int64;
function ked(x:int64):int64;
var i:longint;
begin
if x=0 then ked:=0
else if x>=1 shl 18 then ked:=ked(x shr 18)+ked(x and((1 shr 18)-1))
else
if f[x]>0 then ked:=f[x]
else begin
i:=x;
while i>0 do
begin
f[x]:=f[x]+1;
i:=i and(i-1);
end;
ked:=f[x];
end;
end;
function time(l,r:int64):int64;
var i:longint;
begin
i:=r;
if (wrem[ked(l),r]<>0) then time:=wrem[ked(l),r]
else begin
while r<(1 shl 18) do
begin
r:=r+ked(l)+ked®;
inc(wrem[ked(l),i]);
end;
time:=wrem[ked(l),i];
r:=r-(1 shl 18);

ost[ked(l),i]:=r;
end;
end;

begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n,k);
l:=n shr 18;
r:=n and ((1 shl 18)-1);
i:=0;
while r<(1 shl 18) do
begin

r:=r+ked(l)+ked®;
inc(i);
if i=k then break;
end;
if i<k then begin
inc(l);
r:=r-(1 shl 18);
while (i+time(l,r))<k do
begin
i:=i+time(l,r);

r:=ost[ked(l),r];
inc(l);
end;
if i<k then
while r<(1 shl 18) do
begin
r:=r+ked(l)+ked®;
inc(i);
if i=k then break;
end;
end;
ans:=l*(1 shl 18)+r;
writeln(ans);
end.