jzoj 1388. 【2012.02.25普及组】探索的奶牛

题目描述

 FJ的奶牛喜欢探索农场周围的地形。一开始，所有N(1<=N<=1,000,000,000)只奶牛一起出发，但当碰到路口时，这一群牛可能会分成两部分(不能为空)，每一部分都继续前进，当碰到另一个路口时，再分成两部分，如此反复下去。。。

-假设路上到处都是新的岔口，计算最终被分成多少支队伍。

 

输入

输出

思路

 

 二分，分别判断奇数和偶数的情况，如果当前数和m不是同一类型的（奇数或偶数）就加一然后退出；

程序

var
  i,j,k,n,m,s:longint;
procedure dfs(l,r,x:longint);
var
  i,j,k:longint;
begin
  if (x<=m+1) or (x mod 2<>m mod 2)
    then begin
           inc(s);
           exit;
         end;
  if (x mod 2)=0 then
  begin
  i:=x div 2-m div 2;
  j:=x div 2+m div 2;
  end
  else
    begin
      i:=x div 2-m div 2;
      j:=x-i;
    end;
  if i+j<>x then begin inc(s); exit; end;
  dfs(l,i,i);
  dfs(j,r,j);
end;
begin
  readln(n,m);
  dfs(1,n,n);
  writeln(s);
end.