首页 > 代码库 > hdu 1517 A Multiplication Game（必胜态，必败态）
hdu 1517 A Multiplication Game（必胜态，必败态）
A Multiplication Game
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5833 Accepted Submission(s): 3303
Problem 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.
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.
Sample Input
1621734012226
Sample Output
Stan wins.Ollie wins.Stan wins.
Source
从最后一个必败态往前找，一直推出初始的状态
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 //a数组存的是从小到大所有的乘积 6 __int64 a[7000]= {1}, min, n; 7 //p[j]存的是待与j相乘的数的下标 8 int p[10], sg[7000], i, j, k; 9 for(i = 2; i < 10; p[i] = 0, i++)10 ;11 //从小到大求出所有乘积12 for(i = 1; i < 7000; i++) {13 //找到最小的乘积14 for(j = 2,min = -1; j < 10; j++) {15 if(min == -1 || a[p[j]] * j < a[p[min]] * min) {16 min = j;17 }18 }19 a[i] = a[p[min]] * min;//20 21 if(a[i] >= 5000000000) {22 break;23 }24 //排除相同的乘积25 for(j = 2; j < 10; j++) {26 if(a[p[j]]*j == a[i]) {27 p[j]++;28 }29 }30 }31 32 // for (i = 0; i < 100; ++i) {33 // printf("%d ", a[i]);34 // }35 36 while(scanf("%I64d",&n) != EOF) {37 for(i=0; i<7000; i++) {38 sg[i] = 0;39 if(a[i] >= n) {40 break;41 }42 }43 for(j = i-1; a[j] * 9 >= n && j >= 0; j--) {44 sg[j] = 1;//必胜45 }46 while(j >= 0) {47 for(k = j+1; k < i && a[j] * 9 >= a[k]; k++)48 if(a[k] % a[j] == 0 && sg[k] == 0) {//找到一个必败态49 sg[j] = 1;//必胜50 break;51 }52 j--;53 }54 puts(sg[0] ? "Stan wins." : "Ollie wins.");55 }56 return 0;57 }
如果找到规律，也很简单
d.两个人玩游戏，给一个数字n，每次操作可以从2~9中任选一个数字，并把它与p相乘，（游戏开始时p=1）
两人轮流操作，当一个人操作完后p>=n，这个人就是胜者。
s.
①、如果输入是2～9，因为Stan是先手，所以Stan必胜。
②、如果输入是10～18(9*2)，因为Ollie是后手，不管第一次Stan乘的是多少，Stan肯定在2～9之间，如果Stan乘以2，那么Ollie就乘以9，那么Ollie乘以大于1的数都能超过10～18中的任何一个数，Ollie必胜。
③、如果输入的是19～162(9*2*9)，那么这个范围Stan必胜。
④、如果输入是163～324(9*2*9*2)，这个是Ollie的必胜范围。
…………
可以发现必胜态是对称的。
如果“我方”首先给出了一个在N不断除18后的得到不足18的数Ｍ，“我方”就可以胜利，然而双方都很聪明，所以这样胜负就决定与Ｎ了，如果Ｎ不断除18后的得到不足18的数Ｍ，如果1＜Ｍ＜＝９则先手胜利，即Stan wins.如果９＜Ｍ＜＝１８则后手胜利。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 int main(){ 8 9 //freopen("input.txt","r",stdin);10 11 double n; //用long long 就不能AC了，求解。。。。。。。。12 while(cin>>n){13 while(n>18)14 n/=18;15 if(n<=9)16 printf("Stan wins.\n");17 else18 printf("Ollie wins.\n");19 }20 return 0;21 }
hdu 1517 A Multiplication Game（必胜态，必败态）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。