ac1034.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1034;
const
  maxn=50000;
  m=10000;
var
  ans:array[1..maxn]of word;
  i,d,t,r:word;
begin
  ans[1]:=1;d:=2;t:=2;r:=2;
  for i:=2 to maxn do begin
    ans[i]:=(ans[i-1]+d) mod m;
    if r>1 then
      dec(r)
    else begin
      d:=(d shl 1) mod m;
      inc(t);
      r:=t;
    end;
  end;
  repeat
    read(i);
    writeln(ans[i]);
  until seekeof;
end.