• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

数学-博弈-5794. 求和游戏

admin

11月 28, 2021

2021-07-11 22:49:52

问题描述:

Alice 和 Bob 玩一个游戏,两人轮流行动,Alice 先手 。

给你一个 偶数长度 的字符串 num ,每一个字符为数字字符或者 ‘?’ 。每一次操作中,如果 num 中至少有一个 ‘?’ ,那么玩家可以执行以下操作:

选择一个下标 i 满足 num[i] == ‘?’ 。
将 num[i] 用 ‘0’ 到 ‘9’ 之间的一个数字字符替代。
当 num 中没有 ‘?’ 时,游戏结束。

Bob 获胜的条件是 num 中前一半数字的和 等于 后一半数字的和。Alice 获胜的条件是前一半的和与后一半的和 不相等 。

比方说,游戏结束时 num = “243801” ,那么 Bob 获胜,因为 2+4+3 = 8+0+1 。如果游戏结束时 num = “243803” ,那么 Alice 获胜,因为 2+4+3 != 8+0+3 。
在 Alice 和 Bob 都采取 最优 策略的前提下,如果 Alice 获胜,请返回 true ,如果 Bob 获胜,请返回 false 。

示例 1:

输入:num = “5023”
输出:false
解释:num 中没有 ‘?’ ,没法进行任何操作。
前一半的和等于后一半的和:5 + 0 = 2 + 3 。
示例 2:

输入:num = “25??”
输出:true
解释:Alice 可以将两个 ‘?’ 中的一个替换为 ‘9’ ,Bob 无论如何都无法使前一半的和等于后一半的和。
示例 3:

输入:num = “?3295???”
输出:false
解释:Bob 总是能赢。一种可能的结果是:
– Alice 将第一个 ‘?’ 用 ‘9’ 替换。num = “93295???” 。
– Bob 将后面一半中的一个 ‘?’ 替换为 ‘9’ 。num = “932959??” 。
– Alice 将后面一半中的一个 ‘?’ 替换为 ‘2’ 。num = “9329592?” 。
– Bob 将后面一半中最后一个 ‘?’ 替换为 ‘7’ 。num = “93295927” 。
Bob 获胜,因为 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7 。
 

提示:

2 <= num.length <= 105
num.length 是 偶数 。
num 只包含数字字符和 ‘?’ 。

问题求解:

?的数量如果为奇数,那么alice必胜,因为最后alice可以决定是否让左右两边相等。

bob胜利的唯一条件是?为偶数,且最后?的diff数量的一半的9的倍数为和的差。其实这也很容易理解,就是?和diff_sum在两边,alice无论怎么出数字,bob都出9 – num。

class Solution:
    def sumGame(self, num: str) -> bool:
        n = len(num)

        def get_cnt(num):
            s = 0
            n = 0
            for c in num:
                if c == "?":
                    n += 1
                else:
                    s += int(c)
            return s, n
        
        s1, n1 = get_cnt(num[:n//2])
        s2, n2 = get_cnt(num[n//2:])
        return (n1 + n2) % 2 == 1 or (n2 - n1) // 2 * 9 != s1 - s2

  

发表回复

您的电子邮箱地址不会被公开。