我怎么知道什么时候没有解决方案？算法任务

Question

简而言之，给出这样的问题：

我们加载玩家数量，

每个玩家的钱，

然后我们加载一个由 L i W

组成的字符串

例如：

4 -> 玩家的

2、3、2、1

第一个玩家 2 个钱，第二个玩家 3 个，依此类推

我们加载循环

例如：

WLL -> W == win = cash + 1, L == lost = cash -1;

如果其中一位玩家的钱用完了，则中断游戏，给出所有玩家的游戏次数。

所以：

循环不断重复，所以，我们有 WLLWLL ... WLL

2、3、2、1

[WLL - 第一个周期] [WLL - 下一个周期]

所以，我们有：

3,2,1,2

下一个：

2,1,2,1

最后：

1,2,1,0

然后我们数一数游戏数 - 12

玩家不输的时候也是这样，你就写-1

所以，

我的问题是：我如何编写一个程序来有效地计算它，如果游戏永远不会结束写 -1？

我有类似的东西：

enter code here

#include<vector>
#include<iostream>
using namespace std;


int main()
{
int n, m, ile_gier;
bool nieskonczonosc = true;
cin >> n;
int tab[n];
for(int i = 0; i < n; i++)
{
    cin >> tab[i];
}
cin >> m;
char znak[m];
cin >> znak;
int przesuniecie = n%m;
for(int i = 0; i < n; i++)
{
    if(znak[i+przesuniecie] == 'W') nieskonczonosc = true;

}
if(nieskonczonosc == true) cout << "-1" << endl;

Answer 1

假设你有 n 个玩家和一个长度为 k 的圆圈，每个玩家拥有的钱都大于 n。因此，下一行将移动 n mod k。现在你可以计算 k 行之后的钱变化（那里的转变肯定是 0）现在你可以计算游戏的状态和游戏即将结束的行数（只有当 n 行之后的所有变化都是正数时）游戏没有结束）之后你可以直接计算它。

PS 您可以通过采用 n/gCd(n,k) 行来改进这一点，因为那里的班次也将为 0。然后你可以计算出所有玩家在 n 轮中最大减少的钱。因此玩家的钱可以在你必须评估一切之前降到这个值.....

编辑：这是一个示例代码...它并不完美，但您应该能够理解我的意思...

#include<string>
#include<iostream>
#include<algorithm>

int bruteforce(int nPlayer, int* money, const std::string,int,bool doesEnd);
void calculateWin(int nPlayer, const std::string Cycle, int* changes);
int fastforward(int nPlayer, int* money,int* changes);

int main()
{
    const int nPlayer = 4;
    int money[nPlayer] = { 5,5,5,5 };
    std::string Cycle = "WLL";

    int changes[nPlayer];

    calculateWin(nPlayer, Cycle, changes);

    bool doesEnd = false;
    for (int i = 0; i < nPlayer;i++)
        if (changes[i] < 0)
        {
            doesEnd = true;
            break;
        }



    if (doesEnd)
    {
        int fast = 0;
         fast = fastforward(nPlayer, money, changes);
        std::cout << "Games: " << fast*Cycle.length()*nPlayer+ bruteforce(nPlayer, money, Cycle, 0, 1) << std::endl;
    }
    else
    {
        int games = bruteforce(nPlayer, money, Cycle, 0, 0);
        if (games == -1)
            std::cout << "The Game will not end" << std::endl;
        else
            std::cout << "Games: " << games<<std::endl;
    }

    system("pause");

}

int bruteforce(int nPlayer, int* money, const std::string Cycle, int offset,bool doesend)
{
    int nGames = 0;
    int player = 0;
    while (true)
    {
        player %= nPlayer;
        offset %= Cycle.length();
        for (int i = 0; i < nPlayer;i++)
            if (money[i] <= 0) return nGames;
        money[player] += Cycle[offset] == 'W' ? 1 : -1;
        player++;
        offset++;
        nGames++;
        if (!doesend&&nGames == nPlayer*Cycle.length())return -1;


    }
}


void calculateWin(int nPlayer, const std::string Cycle, int* changes) // calculates the changes after nPlayer*Cycle.length() Games
{
    int shift = nPlayer % Cycle.length();
    for (int i = 0; i < nPlayer;i++)
    {
        changes[i] = 0;
        for (int j = 0;j < Cycle.length();j++)
            changes[i]+= Cycle[(j*shift+i)%Cycle.length()] == 'W'?1:-1;

    }
}

int fastforward(const int nPlayer, int* money, int* changes)
{

    int res = 2147483647; // max int 

    for (int i = 0; i < nPlayer;i++)
    {
        if(changes[i]<0)
            res = std::min( (money[i] - nPlayer) / -changes[i],res);
    }
    if (res < 0)
        return 0;


    for (int i = 0; i < nPlayer; i++)
        money[i] += res * changes[i]; 

    return res;
}

我怎么知道什么时候没有解决方案？算法任务

How can I tell when there are no solutions? Algorithm task

algorithm

math

search

game-theory