如何判斷何時沒有解決方案？算法任務

Question

簡而言之，給出了這樣一個問題：

我們裝載的玩家數量，

每種貨幣的球員，

和我們加載由L的字符串I W

例如：

4 - >玩家的

2,3，2，1

2是金錢的第一玩家，3是第二等

和我們加載週期

例如：

WLL - > w^==贏得現金= + 1，L ==丟失=現金-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的一個cicle每個玩家有足夠的資金越大，然後n。 因此，下一行將被移位n模k。現在你可以計算k行後的金錢變化（那裏的變化肯定是0），現在你可以計算遊戲的狀態和遊戲即將結束的行數（只有當n行後的所有變化都是正數時遊戲不會結束）之後，你可以直接計算它。

PS可以通過取N/GCD（N，K）行改善這一點，因爲那裏的移位爲0，以及。你可以計算n輪所有玩家的最大減少金錢。因此，玩家的錢可以踏踏實實地這個值，你必須EVAL之前的一切.....

編輯：這是一個示例代碼......它並不完美，但你應該能理解我..... .....

#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; 
}