1425A. Arena of Greed

games/greedy, 1400, https://codeforces.com/problemset/problem/1425/A

Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing N gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:

Take one gold coin from the chest.
Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even.

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.

Input

The first line contains a single integer T (1≤T≤10^5^) denotes the number of test cases.

The next T lines each contain a single integer N (1≤N≤10^18^).

Output

T lines, each line is the answer requested by Mr. Chanek.

Example

input

2
5
6

output

2
4

Note

For the first case, the game is as follows:

Mr. Chanek takes one coin.
The opponent takes two coins.
Mr. Chanek takes one coin.
The opponent takes one coin.

For the second case, the game is as follows:

Mr. Chanek takes three coins.
The opponent takes one coin.
Mr. Chanek takes one coin.
The opponent takes one coin.

思路：为了获取最多的石子数量：

数量为奇数时：只能取1个，然后对手进入情况2，我们只能取剩下的；
数量为偶数时：为了尽可能最大化所能取的石子数量，我们尽可能使得对手只能取1个，即使得对手取时数量为奇数；同时使得我们取石子时数量为偶数。为了实现这个情况，判断一下当前石子数量的一半是否为奇数，如果是，我们就取一半；如果不是，我们就取一个，对应的，对手也只能取一个，之后所得到的偶数一般必然是个奇数。证明略。
此外1和4是特殊情况，需要特判一下。

PyPy 3 AC. Python 3 Time limit exceeded on Test2.

python

#input=__import__('sys').stdin.readline
ans = []
def solve(n):
    
    f = s = 0 # To distinguish between first and second hands.
    fs = True
    
    if n & 1:
        n -= 1
        fs = False
        
    while n:
        if n == 4:
            f += 3
            s += 1
            n = 0   # Special Judge
        elif (n//2) & 1: # The First Situation
            f += n//2
            s += 1
            n = (n//2) - 1;
        else:                   #The Second Situation
            f += 1
            s += 1
            n -= 2
    #print( [s+1, f][fs] )
    ans.append( [s+1, f][fs] )
 
 
coins = []
for _ in range(int(input())):
    coins.append(int(input()))
 
for i in coins:
    if i==1:
        ans.append(1)
        #print(1)
    else:
        solve(i)
 
print('\n'.join(map(str, ans)))

python提交超时了，简单优化是数据整体读入，一起处理。可以AC。

python

import sys
input = sys.stdin.read

def solve(n):
    f = s = 0  # To distinguish between first and second hands.
    fs = True

    if n & 1:
        n -= 1
        fs = False

    while n:
        if n == 4:
            f += 3
            s += 1
            n = 0  # Special case
        elif (n // 2) & 1:  # The First Situation
            f += n // 2
            s += 1
            n = (n // 2) - 1
        else:  # The Second Situation
            f += 1
            s += 1
            n -= 2
    ans.append([s + 1, f][fs])

data = input().split()
t = int(data[0])
coins = list(map(int, data[1:t + 1]))

ans = []
for i in coins:
    if i == 1:
        ans.append(1)
    else:
        solve(i)

print('\n'.join(map(str, ans)))

2020fall-cs101，施惟明。

解题思路：简单试验可得，拿到偶数币时，除 4外，最优解法均为使对方拿到奇数币而只能取走一个；拿到奇数币时无法决策，被对方“控场”，对方获得币数-1的最优解。故据此进行迭代。

PyPy3 AC

python

ans = []
def solve(n):
    
    f = s = 0 # To distinguish between first and second hands.
    fs = True
    
    if n & 1:	#如果起始硬币数量为奇数，那么先手方能拿到的最多硬币数转化为后手方的情形
        n -= 1
        fs = False
        
    while n:
        if n == 4:
            f += 3
            s += 1
            n = 0   # Special Judge
        elif (n//2) & 1: # The First Situation
            f += n//2
            s += 1
            n = (n//2) - 1;
        else:                   #The Second Situation
            f += 1
            s += 1
            n -= 2
    #print( [s+1, f][fs] )
    ans.append( [s+1, f][fs] )
 
 
coins = []
for _ in range(int(input())):
    coins.append(int(input()))
 
for i in coins:
    if i==1:
        ans.append(1)
        #print(1)
    else:
        solve(i)
 
print('\n'.join(map(str, ans)))

2020fall-cs101，李元锋。

思路：了解过博弈论的经典游戏的人应该可以很快写出代码。此游戏为完全信息博弈，故如果存在最优解，则所有玩家采取的策略是一样的，策略为让对方为奇数 > 让自己拿偶数，这里只有 4为特例，要注意，剩下的很简单就写出来了，麻烦在于超时，改了很多次才 AC，这里顺便学了一下异或运算来区别是谁的回合。

python

output = []
for i in range(int(input())):
    n=int(input())
    ans, flag = 0, 1
    while n:
        test = 0
        if n%2==0 and n//2%2 or n==4:
            n //= 2
            test = n
        else:
            n -= 1
            test = 1
        if flag:
            ans += test
        flag ^= 1
    output.append(ans)
print('\n'.join(map(str,output)))

递归实现，pypy可以AC。

python

# 刘家亦 24
import sys
#from functools import lru_cache
 
# 设置递归深度限制
sys.setrecursionlimit(30000)
 
 
#@lru_cache(maxsize=None)
def find_the_ans(n):
    if n == 1:
        return 1
    if n == 4:
        return 3
    if n % 2 == 0 and n % 4 != 0:
        return n - find_the_ans(n // 2)
    else:
        return n - find_the_ans(n - 1)
 
 
if __name__ == "__main__":
    # 读取所有输入数据
    input_data = sys.stdin.read().strip()
    lines = input_data.split('\n')
 
    T = int(lines[0])
    ans = []
 
    for i in range(1, T + 1):
        N = int(lines[i])
        ans.append(find_the_ans(N))
 
    # 打印结果
    print(*ans, sep='\n')

1425A. Arena of Greed ​

1425A. Arena of Greed