hdu学校はれんがを運ぶ試合をします

2177 ワード
http://acm.hdu.edu.cn/contests/contest_showproblem.php?cid=638&pid=1001
れんがを運ぶ
Problem Description
  小明は今では人に好かれ、花见の花が咲く高富帥で、美女に囲まれた笙の歌の妙舞に一日中浸っています.しかし人々は何かを知らないで、春風得意の小明もかつて1段の苦しい奮闘の歴史を持っていました.
  あの時の明さんはまだ長い髪を切っていませんでした.クレジットカードがなくて、彼女がいません.24時間のお湯がない家です.でも、初めの明さんはあんなに楽しかったです.破れたギターが一本もないのに…
  なぜ楽しいかというと、その時の明さんは夢を逆襲したからです.ある日、明は彼の心の中の女神の誕生日プレゼントを買うために、ある建築現場に来てレンガを運んでお金を稼ぎました.この時、工事現場からまたトラックのれんがががが運ばれてきました.請負業者は明さんにトラックから下ろしたれんがを一つに分けてもらいました.ベテランの運送屋として、明さんはいつもレンガを一つずつ二つの山に分けています.この時に消耗した体力はスペアレンガの数の差があります.
  今、トラックで運ばれてきたレンガの数が分かりましたが、少なくともどれぐらいの体力で請負業者が要求する任務を達成できるか教えてください.
 
Input
入力データの最初の行は正の整数T(T<=100)で、Tグループのテストデータがあることを表しています.
次のT行は各行の正の整数N(=100000万円)で、トラックから運んできたレンガの数を表します.
 
Output
各グループのデータに対して、明ちゃんが任務を遂行するために必要な最低体力数を出力してください.
 
Sample Input

   
   
   
   

    
    
    
    2
4
5
 
Sample Output

   
   
   
   

    
    
    
    0
2
 
一つの数が奇数の場合、二つの山に分けて体力を消耗します.偶数の場合は消費しません.DFSは奇数と偶数の場合を分けて合わせます.2の累乗乗の場合は0点の体力を消耗します.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
#include <map>

using namespace std;
typedef long long LL;

#define N 110000
#define INF 0x3f3f3f3f
#define PI acos (-1.0)
#define EPS 1e-8
#define met(a, b) memset (a, b, sizeof (a))

int sum = 0, k;

int DFS (int n)
{
    if (n == 1 || n == 2 || n == 4) return 0;

    if (n % 2 == 0)
    {
        return 2*DFS(n/2);
    }
    else
        return DFS ((n+1)/2) + DFS (n/2) + 1;
}

int main()
{
    int t, n;
    scanf ("%d", &t);
    while (t--)
    {
        sum = 0, k = 1;
        scanf ("%d", &n);

        printf ("%d
", DFS (n));
    }
    return 0;
}
ES 6 Aray新規API