Решить задачу Района 2008 Временной ключ (прикрепила условие и тесты). Протестировать себя самим.
1
тесты Временной ключ Район 2008
Автор LVP, 15 мая 2013 15:29
Сообщений в теме: 4
#2
Отправлено 22 мая 2013 - 14:00
Кстати количество битов можежет быть 36.
А так всё работает нормально.
А так всё работает нормально.
var time,ost:array[1..20,1..300000]of int64; ed:array[1..300000]of int64; n,k,x,y,l,r,i:int64; function kol(x:int64):int64; var y:longint; begin if x=0 then exit(0); if x<1 shl 18 then begin if ed[x]=0 then begin y:=x; while y>0 do begin y:=y and (y-1);inc(ed[x]); end; end; exit(ed[x]); end; kol:=kol(x shr 18)+kol(x and((1 shr 18)-1)); end; function next(l1,r1:int64):int64; var i:int64; begin if time[kol(l1),r1]>0 then exit(time[kol(l1),r1]); i:=0; while r1<1 shl 18 do begin inc(i);r1:=r1+kol(l1)+kol(r1); end; l1:=l1+1;r1:=r1-(1 shl 18); time[kol(l),r]:=i;ost[kol(l),r]:=r1; exit(i); end; begin assign(input,'input.txt');reset(input); assign(output,'output.txt');rewrite(output); readln(n,k); i:=0;l:=n shr 18;r:=n and ((1 shl 18)-1); while(r<1 shl 18)and(i<k)do begin r:=r+kol(l)+kol(r);; inc(i); end; if i=k then begin writeln((l shl 18)+r);exit;end; l:=l+1;r:=r-(1 shl 18); while i<k do begin x:=next(l,r); if i+x<k then begin i:=i+x;r:=ost[kol(l),r];l:=l+1;continue;end; while(i<k)do begin r:=r+kol(l)+kol(r);;inc(i);end; end; writeln((l shl 18)+r); end.
#3
Отправлено 23 мая 2013 - 16:41
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.
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.
#4
Отправлено 27 мая 2013 - 18:19
Все работает
var n,r,i,k : longint; numberOf1 : array [0..300000] of longint; l : int64; ostr,kol : array [0..300000,0..60] of longint; function no1 (x : longint) : longint; var j : longint; begin if x=0 then exit(0); if x>1 shl 18 then no1:=no1(x shr 18)+no1(x and ((1 shl 18)-1)) else begin if numberOf1[x]>0 then exit(numberOf1[x]); j:=x; while j>0 do begin j:=j and (j-1); numberOf1[x]:=numberOf1[x]+1; end; no1:=numberOf1[x]; end; end; function wrem (x,y : longint) : longint; var i : longint; begin if kol[y,x]>0 then exit(kol[y,x]); i:=y; while i<1 shl 18 do begin kol[y,x]:=kol[y,x]+1; i:=i+no1(i)+x; {if kol[i,x]>0 then begin kol[y,x]:=kol[y,x]+kol[i,x]; ostr[y,x]:=ostr[i,x]; exit(kol[y,x]); end; } end; ostr[y,x]:=i-(1 shl 18); wrem:=kol[y,x]; end; begin // assign(input, 'input.txt'); reset(input); // assign(output, 'output.txt'); rewrite(output); readln(n,k); r:=n and ((1 shl 18)-1); l:=n shr 18; i:=0; while R<1 shl 18 do begin r:=r+no1(l)+no1(r); i:=i+1; if i=k then break; end; if i=k then begin writeln((l shl 18) + r); halt; end; l:=l+1; r:=r-(1 shl 18); while (i+wrem(no1(l),r))<=k do begin i:=i+wrem(no1(l),r); r:=ostr[r,no1(l)]; l:=l+1; end; if i<k then begin while i<k do begin r:=r+no1(l)+no1(r); i:=i+1; end; end; writeln((l shl 18)+r); end.
Yo
#5
Отправлено 28 мая 2013 - 18:06
Рабочий код на С++.
#include <iostream> #include <utility> #define mp make_pair #define F first #define S second typedef long long ll; using namespace std; const int border = 1 << 18; int n, k, r; ll l; int q[500000]; pair <int, int> t[50][270000]; int cnt(ll x) { if (x == 0) return 0; if (x > border) return cnt(x >> 18) + cnt(x & (border - 1)); if (q[x] > 0) return q[x]; int k = 0; ll n = x; while (n > 0) { k++; n = n & (n - 1); if (q[n] > 0) { k += q[n]; break; } } q[x] = k; return k; } int main() { cin.sync_with_stdio(false); cout.sync_with_stdio(false); cin >> n >> k; r = n & (border - 1); l = n >> 18; int i = 0, j = 0, x = 0; while (i < k) { int temp = cnt(l); if (t[temp][r].F > 0) { if (i + t[temp][r].F < k) { i += t[temp][r].F; r = t[temp][r].S; ++l; j = 0; x = r; continue; } } r += cnt(r) + temp; ++j; ++i; if (r > border) { t[temp][x].F = j; t[temp][x].S = r - border; r = r - border; ++l; j = 0; x = r; } } cout << (l << 18) + r; return 0; }
Количество пользователей, читающих эту тему: 1
0 пользователей, 1 гостей, 0 анононимных