HDU 1517 A Multiplication Game 巴什博弈
生活随笔
收集整理的這篇文章主要介紹了
HDU 1517 A Multiplication Game 巴什博弈
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題意:2 個人玩游戲,給定一個數(shù)n,從 1 開始,輪流對數(shù)進行累乘一個數(shù)(2~9中取),
直到第一次等于或超過n為贏.
思路:1)找規(guī)律
如果n是 2 ~ 9 ,Stan 必勝。
如果輸入是 10~18 ,不管第一次Stan 乘的是什么,Stan肯定在 2 ~ 9 之間,
無論stan乘以什么,Ollie乘以大于1的數(shù)都都能超過 10 ~ 18 中的任何一個數(shù)。Ollie 必勝。
如果輸入是 19 ~ 162,那么這個范圍是 Stan 的必勝態(tài)。
如果輸入是 163 ~ 324 ,這是又是Ollie的必勝態(tài)。
............
必勝態(tài)是有規(guī)律可循的。
如果"我方"首先給出了一個在n不斷除18后的得到不足18的
數(shù)m,"我方"就可以取得勝利,然而雙方都很聰明,所以這樣勝負就決定于n了,
如果n不斷除18后的得到不足18的數(shù)m,
若1<m<=9則先手勝利,
若9<m<=18則后手勝利.
Description
Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.?Input
Each line of input contains one integer number n.?Output
For each line of input output one line either?Stan wins.?
or?
Ollie wins.?
assuming that both of them play perfectly.?
Sample Input
162 17 34012226Sample Output
Stan wins. Ollie wins. Stan wins. 一道巴什博弈的轉(zhuǎn)化題目其實差不多以前是加法現(xiàn)在是乘法了,不過沒有想到用double導致錯了好多次。。。。 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; int main() {double n;while(~scanf("%lf",&n)){while(n>18){n/=18;}if(n<=9)printf("Stan wins.\n");elseprintf("Ollie wins.\n");}return 0; }總結(jié)
以上是生活随笔為你收集整理的HDU 1517 A Multiplication Game 巴什博弈的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: iframe 嵌入dom结构处理
- 下一篇: Day215.课程详细页面功能完善、Ec