首頁 Uva Problems

# 題目: UVa 11489 - Integer Game

# 題目說明

有兩位玩家 S 與 T 要玩一個回合制遊戲，由 S 先行動
從 N 開始，每位玩家要輪流移除一個字元的數字
條件為:

  1. 移除後所有數字相加需要為 3 的倍數
  2. 當剩餘一個數字時，可以直接移除
    誰先不能移除數字誰就輸了

例如當 N = 1234
可以移除 4 ，會使得剩下的數字 1 + 2 + 3 = 6 為 3 的倍數
也可以移除 1 ，會使得剩下的數字 2 + 3 + 4 = 9 也為 3 的倍數

INPUT:
第一行輸入一個整數 T ，代表測資數
每筆測資輸入一個整數 N

OUTPUT:
輸出 S (S 贏) 或 T (T 贏)

# 解題方法

先將 N 存入一個 vector<int> num ，每個字元一位
設一個變數 sum 為 num 的數字合
判斷 sum - num[i] 是否為 3 的倍數，是則移除那個數字並換另一個玩家行動
重複做至當 num 剩餘一個數字或 sum - num[i] 沒有找到 3 的倍數

# 參考程式碼

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	string N;
	cin >> T;
	for (int cases = 1; cases <= T; ++cases) 
	{
		bool s_win = false;
		vector<int> num;
		cin >> N;
		for (auto& c : N) num.emplace_back(c - '0');
		
		while (1)
		{
			int sum = 0;
			for (auto& i : num) sum += i;
			int i = 0;
			for (; i < num.size(); ++i) if ((sum - num[i]) % 3 == 0)
			{	
				s_win ^= 1;
				num.erase(num.begin() + i);
				break;
			}
			if (num.size() == 1)
			{
				s_win ^= 1;
				break;
			}
			if (i == num.size()) break;
		}
		cout << "Case " << cases << ": " << (s_win ? "S" : "T") << "\n";
	}
	return 0;
}