UVALive 3668 A Funny Stone Game(博弈)
Description
The funny stone game is coming. There are n piles of stones, numbered with 0, 1, 2,..., n - 1. Two persons pick stones in turn. In every turn, each person selects three piles of stones numbered i, j, k (i < j, jk and at least one stone left in pile i). Then, the person gets one stone out of pile i, and put one stone into pile j and pile k respectively. (Note: if j = k, it will be the same as putting two stones into pile j). One will fail if he can't pick stones according to the rule.
David is the player who first picks stones and he hopes to win the game. Can you write a program to help him?
The number of piles, n, does not exceed 23. The number of stones in each pile does not exceed 1000. Suppose the opponent player is very smart and he will follow the optimized strategy to pick stones.
Input
The last case is followed by a line containing a zero.
Output
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std; const int MAXN = ; int sg[MAXN + ];
bool mex[MAXN * MAXN];
int n, s[MAXN]; void build_sg() {
for(int i = MAXN - ; i >= ; --i) {
memset(mex, , sizeof(mex));
for(int j = i + ; j < MAXN; ++j) {
for(int k = j; k < MAXN; ++k) mex[sg[j] ^ sg[k]] = true;
}
for(int j = ; ; ++j)
if(!mex[j]) {sg[i] = j; break;}
}
} void solve() {
int ans = , *sg = ::sg + MAXN - n;
for(int i = ; i < n; ++i) ans ^= sg[i] * (s[i] & );
if(ans == ) {
printf(" -1 -1 -1\n");
return ;
}
for(int i = ; i < n; ++i) {
if(s[i] == ) continue;
for(int j = i + ; j < n; ++j) {
for(int k = j; k < n; ++k) {
if((sg[i] ^ sg[j] ^ sg[k] ^ ans) == ) {
printf(" %d %d %d\n", i, j, k);
return ;
}
}
}
}
} int main() {
build_sg();
int cnt = ;
while(scanf("%d", &n) != EOF && n) {
for(int i = ; i < n; ++i) scanf("%d", &s[i]);
printf("Game %d:", ++cnt);
solve();
}
}
最新文章
- echarts一个页面动态加载两张不同图表数据
- C# 计时器
- MYSQL将表名称修改成大写的存储过程
- STL(pair map set vector priority_queue) poj 3297
- WordPress Contact Form 7插件任意文件上传漏洞
- 关于pagerank算法的一点点总结
- 解决XCode插件在XCode6.4上失效的办法
- 支付宝即时到账DEMO配置与使用
- sql server 高可用镜像
- 搭建docker私有仓库(https)
- faiss索引基于数量级和内存限制的选择
- 解码base64加密的图片并打印到前台
- 解决kali linux 升级后安装w3af 问题
- json-server基本使用
- 深入JVM之类的加载过程
- Web API 2 对于 Content-Length 要求严格
- parallelogram
- 【C++】atoi与stoi
- Java applets A Java applet example
- ES6 之 解构赋值