NOT A BLOG | sqybi

SGU 175 — Encoding

Posted on 五月 25th, 2008.

稍微推导一下就可以得到一个递推式(这里直接借用WindyWinter的式子):
pos[1,1]=1
pos[n,q]=n-k+pos[k,k-q+1] (q<=k)
             =pos[n-k,n-q+1] (q>k)

求pos[n, q]即可.

{
SGU 175; Encoding
- sqybi’s code
}
//for my winsty
program sgu175_sqybi;
  var
    n, t, q, k: longint;

  begin
    readln(n, q);
    t := 0;
    while n <> 1 do begin
      k := n div 2;
      if q <= k then begin
        t := t + n - k;
        n := k;
        q := k - q + 1;
      end
      else begin
        q := n - q + 1;
        n := n - k;
      end;
    end;
    t := t + 1;
    writeln(t);
  end.

阅读(110 次)

Make a Comment

Make A Comment: ( 1 so far )

One Response to “SGU 175 — Encoding”

Comments RSS Feed

Where's The Comment Form?