(Hackerrank) (Game of Stones) 如果未指定条件，我如何找到答案

Question

https://www.hackerrank.com/challenges/game-of-stones-1/problem

石头游戏

两个叫 P1 和 P2 的玩家正在玩一个有起始数量的棋子的游戏。玩家 1 始终先下棋，两名玩家轮流移动。游戏规则如下：

在一次移动中，玩家可以从游戏板上移除 2、3 或 5 颗宝石。如果玩家无法移动，则该玩家输掉游戏。给定石头的起始数量，找到并打印获胜者的名字。 P1 被命名为 First，P2 被命名为 Second。每个玩家都以最佳方式玩，这意味着如果存在获胜动作，他们将不会做出导致他们输掉比赛的动作。

例如，如果n = 4，P1可以进行如下走法：

P1 移除 2 颗棋子，剩下 2 颗棋子。P2 将移除 2 颗棋子并获胜。 P1 移除 3 个石头，留下 1 个。P2 无法移动并输掉。 P1 将进行第二次比赛并赢得比赛。

函数说明

在下面的编辑器中完成 gameOfStones 函数。它应该 return 一个字符串，First 或 Second。

gameOfStones 具有以下参数：

n: 一个整数，代表石头的起始数量

输入格式

第一行包含一个整数，测试用例的数量。接下来的每一行都包含一个整数，即测试用例中石头的数量。

约束条件

1<= n,t <= 100

输出格式

如果第一个玩家获胜，则在每个测试用例的新行上打印 First。否则打印 Second.

我的问题

在 link 的文档中，玩家每回合可以拿走 2、3 或 5 个石头。

但是，如果每个案例的石头数量和条件数量不同，我该如何编写代码？

例如。情况1，玩家可以拿走2、3、5个石头，情况2，玩家可以拿走2、4、7、9个石头。

并且代码将通过这两种情况。

输入案例 1：

3  //total conditions of stones can take
2 3 5 //player can take 2, 3 or 5 stones
8 // Number of cases of number of starting stones
1
2
3
4
5
6
7
10

案例二：

4  //total conditions of stones can take
2 3 7 9 //players can take 2, 3,7 or 9 stones
5 // Number of cases of number of starting stones
5
6
7
10
15

并且代码将通过这两种情况。满足这种情况的编码应该怎么写？

Answer 1

我在 Swift 中写下了您的新问题的解决方案。如果您不熟悉它，希望它与您使用的语言足够相似以便有用。

这是一般情况下的解决方案。

// This is an internal function that also takes a dictionary of results so that
// it can remember solutions it has already found
func game(n: Int, conditions: [Int], result: inout [Int : String]) -> String {

    // Have we seen this answer before?  If so, just return it
    if let answer = result[n] {
        return answer
    }

    if n < conditions.min()! {
        // I can't move because the number of stones left is fewer than
        // I'm allowed to take
        result[n] = "Second" // to speed up the solution, remember this result
        return "Second"
    } else if conditions.contains(n) {
        // I can take all of the stones, so I win
        result[n] = "First"  // to speed up the solution, remember this result
        return "First"
    } else {
        // Try taking each of the stones I'm allowed to take, and see
        // if that causes my opponent to lose
        for take in conditions {
            let leave = n - take

            // If the number of stones I leave causes the opponent to lose, I win
            if leave > 0 && game(n: leave, conditions: conditions, result: &result) == "Second" {
                result[n] = "First" // to speed up the solution, remember this result
                return "First"
            }
        }
    }
    
    // No way for me to win, so I come in second.
    result[n] = "Second"  // to speed up the solution, remember this result
    return "Second"
}

// Generate a dictionary to store already generated answers, and call the
// internal recursive routine
func gameOfStones(n: Int, conditions: [Int]) -> String {
    var result = [Int : String]()
    
    return game(n: n, conditions: conditions, result: &result)
}

print(gameOfStones(n: 4, conditions: [2, 3, 5]))   // "First"
print(gameOfStones(n: 6, conditions: [3, 7, 13]))  // "Second"

(Hackerrank) (Game of Stones) 如果未指定条件，我如何找到答案

(Hackerrank) (Game of Stones) How could i find answer if unspecified condition

algorithm

game-theory