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.

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

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

當寶箱金幣數量為0時，遊戲結束。他們都試圖得到這最大的金幣數量，且他們都玩得最優，問$Chanek$能獲得的最大金幣數。

解題思路： 既然是最優問題，我們就要思考，什麼時候最優，如果我可以進行第二步操作，那麼我們是不是傾向於進行第二步操作。 因為這樣的收益是目前最大的。當然，這隻考慮到你自己，你沒有考慮到別的因素。如果我們進行完第二步操作後，別人只能進行第一步操作，而你又能進行第二步操作這是不是最優的？當然是，那麼這種情況其實就是$4$的倍數的時候，考慮到這個我們則可以進行選擇了，在模擬回合的時候我們要變換角色，可以通過01互斥或來解決該問題，同時我們也只需要統計$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;
}