[原題描述]

Description

Bob is very famous because he likes to play games. Today he puts a chessboard in the desktop, and plays a game with Alice. The size of the chessboard is n by n. A stone is placed in a corner square. They play alternatively with Alice having the first move. Each time, player is allowed to move the stone to an unvisited neighbor square horizontally or vertically. The one who can’t make a move will lose the game. If both play perfectly, who will win the game?

Input

The input is a sequence of positive integers each in a separate line. The integers are between 1 and 10000, inclusive, indicating the size of the chessboard. The end of the input is indicated by a zero.

Output

Output the winner (“Alice” or “Bob”) for each input line except the last zero. No other characters should be inserted in the output.

Sample Input

2
0
Sample Output

Alice

解題思路：

這個(gè)是一個(gè)策略問(wèn)題，往往這種題目用一般的算法都是很難解決的。但是用數(shù)學(xué)的方法可能會(huì)更好理解一點(diǎn)。
方法：用1*2形狀的骨牌放整個(gè)圖
解析：很多人可能會(huì)問(wèn)了，為什么要用上面的骨牌呢？其實(shí)理由很簡(jiǎn)單。
這是一個(gè)雙方博弈的問(wèn)題。我們先要求Alice的起始點(diǎn)和第一步走的點(diǎn)可以形成一個(gè)1*2的骨牌(可以理解為一個(gè)矩形)。
上面的假設(shè)是合理的。因?yàn)橐苿?dòng)方法只能是水平的，或者是垂直的。所以，結(jié)果是無(wú)論在起始點(diǎn)上選擇怎么移動(dòng)，都可以理解為是在一個(gè)已有的1*2的骨牌(矩陣內(nèi)部移動(dòng))。
起始問(wèn)題解決了
那么按照這樣的思路，對(duì)于Bob要做的事情，就是不斷地去從一個(gè)骨牌去找到新的骨牌，而，對(duì)于Alice就是在Bob已經(jīng)找好的骨牌內(nèi)部移動(dòng)。
有人可能會(huì)問(wèn)了，為什么確保了Bob進(jìn)入的一定是一個(gè)骨牌呢？(就是說(shuō)，為什么在Bob走完之后，Alice一定能走呢？)
這個(gè)問(wèn)題很對(duì)，其實(shí)，這時(shí)候就需要判斷了(而這個(gè)就是這個(gè)程序的唯一要考慮的地方)。
因?yàn)槲覀兒芮宄?#xff0c;一旦確保了Bob每次進(jìn)入的都是一個(gè)新的沒(méi)有走過(guò)的骨牌，那么Alice的百分百贏的。(Bob負(fù)責(zé)在找新的骨牌，找到了Alice就去骨牌的另外一個(gè)位置就好了嘛)
判斷方法其實(shí)很簡(jiǎn)單，就是判斷整個(gè)圖是否可以被1*2的骨牌完全覆蓋

先看上面的整個(gè)圖片，這是一個(gè)4*4的正方形(題目說(shuō)了，圖都是正方形)
我們是能找到這樣的一個(gè)圖的用1*2的骨牌覆蓋的方法的。就是如下：

這其實(shí)只是其中的一種分類方法。但已經(jīng)說(shuō)明了可以用1*2的骨牌進(jìn)行完全覆蓋。
要知道，Alice是負(fù)責(zé)在一個(gè)Bob已經(jīng)走過(guò)的骨牌中走，保證了Bob不能在這個(gè)骨牌中走，讓Bob如果不想輸?shù)舯荣?#xff0c;就必須要去找到新的骨牌。
上面是張”偶數(shù)偶數(shù)”的圖，下面看一張”奇數(shù)奇數(shù)”的圖

這個(gè)圖是安排不了一個(gè)關(guān)于1*2的骨牌的全覆蓋的。原因是奇數(shù)乘于奇數(shù)還是奇數(shù)。那么就不能被偶數(shù)整除。

像上圖一樣。
那么這時(shí)候情況就反過(guò)來(lái)了。之前我們說(shuō)Alice只需要在Bob找到的骨牌中移動(dòng)，確保了Bob不能走回到這個(gè)舊的骨牌就好了，那么最后Alice就是穩(wěn)贏了。但上面的推理，其實(shí)在偶數(shù)的情況才成立
對(duì)于上面的一樣，如果是奇數(shù)的呢？
我們就可以理解為，顯示Alice在從起始點(diǎn)走，那么Bob就在Alice走過(guò)的那個(gè)骨牌內(nèi)部走這樣的假設(shè)合理的，因?yàn)樵诖_保了這個(gè)圖在減去一個(gè)點(diǎn)之后，是可以被一個(gè)1*2的骨牌全覆蓋的時(shí)候，那么Bob就可以說(shuō)是在原來(lái)的Alice走的骨牌上進(jìn)行移動(dòng)了，確保Alice不能在這個(gè)舊的骨牌內(nèi)部走。

最終的代碼：(只需要判斷n是個(gè)奇數(shù)還是偶數(shù)就好了)

#include <iostream> using namespace std; int main(){int n;while (cin >> n && n) {cout << (n%2==0? "Alice\n":"Bob\n");} }

最后，老套路，宣傳一波自己的公眾號(hào)！（求關(guān)注哇！）
本人中大一肥宅，歡迎大家關(guān)注，請(qǐng)掃下面的二維碼(〃’▽’〃)

如果覺(jué)得有幫助的話，可以掃碼，贊賞鼓勵(lì)一下！謝謝！

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Sicily1798. Alice and Bob[策略问题]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。