CF1425A Arena of Greed
题目描述
最近，Mr. Chanek 经常玩一款名为 Arena of Greed 的游戏。顾名思义，这款游戏的目标是找出最贪婪的人，他将被加冕为 Compfestnesia 的国王。
这款游戏由两个人轮流进行，Mr. Chanek 先手。最初，宝箱中有 $N$ 枚金币。当宝箱中没有金币时，游戏结束。在每一回合，玩家可以进行以下两种操作之一：
- 从宝箱中取出一枚金币。
- 取出宝箱中一半的金币。只有当宝箱中的金币数量为偶数时，才能进行此操作。
两位玩家都会尽力让自己获得的金币数量最大化。Mr. Chanek 想请你帮忙计算，如果双方都采取最优策略，他最终最多能获得多少金币。
输入格式
第一行包含一个整数 $T$ $(1 \le T \le 10^5)$，表示测试用例的数量。
接下来的 $T$ 行，每行包含一个整数 $N$ $(1 \le N \le 10^{18})$。
输出格式
输出 $T$ 行，每行一个答案，表示 Mr. Chanek 能获得的最大金币数。
说明/提示
对于第一个样例，游戏过程如下：
1. Mr. Chanek 取走一枚金币。
2. 对手取走两枚金币。
3. Mr. Chanek 取走一枚金币。
4. 对手取走一枚金币。
对于第二个样例，游戏过程如下：
1. Mr. Chanek 取走三枚金币。
2. 对手取走一枚金币。
3. Mr. Chanek 取走一枚金币。
4. 对手取走一枚金币。
由 ChatGPT 4.1 翻译