A. Arena of Greed（博弈+貪心）2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest

原題鏈接： https://codeforces.com/problemset/problem/1425/A

測驗樣例

input
2
5
6
output
2
4

Note

For the first case, the game is as follows:

1. Mr. Chanek takes one coin.
2. The opponent takes two coins.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

For the second case, the game is as follows:

1. Mr. Chanek takes three coins.
2. The opponent takes one coin.
3. Mr. Chanek takes one coin.
4. The opponent takes one coin.

題意： 現在 C h a n e k Chanek Chanek和對手玩一個博弈游戲，規則是這樣，有一個寶箱中含有 n n n個金幣，每個人互動進行一回合， C h a n e k Chanek Chanek先開始，進行操作有兩種選擇：

• 你可以拿走一個金幣
• 如果寶箱中金幣數量為偶數，你可以拿走寶箱金幣的一半，

當寶箱金幣數量為0時，游戲結束，他們都試圖得到這最大的金幣數量，且他們都玩得最優，問 C h a n e k Chanek Chanek能獲得的最大金幣數，

解題思路： 既然是最優問題，我們就要思考，什么時候最優，如果我可以進行第二步操作，那么我們是不是傾向于進行第二步操作， 因為這樣的收益是目前最大的，當然，這只考慮到你自己，你沒有考慮到別的因素，如果我們進行完第二步操作后，別人只能進行第一步操作，而你又能進行第二步操作這是不是最優的？當然是，那么這種情況其實就是 4 4 4的倍數的時候，考慮到這個我們則可以進行選擇了，在模擬回合的時候我們要變換角色，可以通過01異或來解決該問題，同時我們也只需要統計 C h a n e k Chanek Chanek的硬幣數即可，

AC代碼

/*
*郵箱：unique_powerhouse@qq.com
*blog:https://me.csdn.net/hzf0701
*注：文章若有任何問題請私信我或評論區留言，謝謝支持，
*
*/
#include<bits/stdc++.h>	//POJ不支持

#define rep(i,a,n) for (int i=a;i<=n;i++)//i為回圈變數，a為初始值，n為界限值，遞增
#define per(i,a,n) for (int i=a;i>=n;i--)//i為回圈變數， a為初始值，n為界限值，遞減，
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pair

using namespace std;

const int inf = 0x3f3f3f3f;//無窮大
const int maxn = 1e5;//最大值，
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割線，以上為自定義代碼模板***************************************//

ll t,n;
int main(){
	//freopen("in.txt", "r", stdin);//提交的時候要注釋掉
	IOS;
	while(cin>>t){
		while(t--){
			cin>>n;
			ll ans=0;
			ll player=0;//0代表Chanek，1代表Arena，
			//開始游戲，利益最大化，
			while(n){
				if(n%2){
					if(player==0){
						ans++;
					}
					n--;
				}
				else{
					if(n==4||(n>4&&n%4!=0)){
						if(player==0){
							ans+=n/2;
						}
						n/=2;
					}
					else{
						if(player==0){
							ans++;
						}
						n--;
					}
				}
				player^=1;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}