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

发布于 2019-03-18  12 次阅读


 

题目描述

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

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

 

输入

 第1行: 两个用空格隔开的整数:N,K

输出

第1行: 输出一个整数表示最终的队伍数。

思路

 

 二分,分别判断奇数和偶数的情况,如果当前数和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.

 

]]>


「墨泼三千烟火,许你一世迷离」