UVa 11489 Integer Game

http://uva.onlinejudge.org/external/114/11489.html
題意：
　　由S先開始，每次拿掉一個數字都要使得剩下的"位數和"是3的倍數，如果找不到數字拿掉就輸了。

想法：
　　我們知道如果數字和為3的倍數，那麼接下來要拿掉的數字必須為3的倍數，才能繼續使得數字和為3的倍數。本題可將一連串的數字分成兩組：3的倍數和非3的倍數，然後有3種情況：

1. 如果非3倍數的數字和是3的倍數：那麼只要看3的倍數的數字個數是奇數個還偶數個就能決定贏家，因為當拿完3的倍數的數字後就無法再拿任何數字了。
2. 如果非3倍數的數字和不是3的倍數：
   那麼需要確認是否能從非3倍數的數字中找出使得數字和為3的倍數，
   ＊如果找的到，那麼就可以回到狀況1
   ＊如果找不到，代表是T獲勝，因為從一開始就無法拿掉任何數字。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int T,Case=1;
	scanf("%d",&T);
	getchar();
	while (T--){
	int N[1001],nOfN=0; //用來存非3的倍數的數字
	int nOf3x = 0; //該位數為3的倍數的個數
	int sum = 0; //非3倍數的和
	while (1){
	char c = getchar();
	if (c == '\n') break;
	else if ((c-'0')%3 == 0) nOf3x++;
	else {
	N[nOfN++] = (c-'0');
	sum += (c-'0');
	}
	}
	int who; //who為偶數代表S,奇數代表T
	if (nOf3x % 2) who = 0;
	else who = 1;
	if (sum%3 !=0) {
	int i;
	for (i=0; i<nOfN; i++)
	if ((sum-N[i])%3 == 0) break;
	if (i==nOfN) who=1;
	else who++;
	}
	printf("Case %d: ",Case++);
	if (who % 2) printf("T\n");
	else printf("S\n");
	}
	return 0;
	}

view raw [UVa] 11489 Integer Game.cpp hosted with ❤ by GitHub