小小马
## 描述
鸡尾酒是小小马的粉丝,于是他比较喜欢研究关于“马”的问题。
给你一个n*m的棋盘,每次可以在任意点放一个象棋中的“马”,假设在x,y点放置一个马,则马对应移动的8个位置都不能放置其他马。
即(x+1,y+2),(x-1,y+2),(x+1,y-2),(x+1,y-2),(x+2,y-1),(x+2,y+1),(x-2,y+1),(x-2,y-1)这八个点都不能再放置马。
鸡尾酒邀请了wls来玩这个游戏,wls先手,首先无法操作的人输。
假设对阵双方都玩得很好,请问谁会赢得这场比赛。
## 输入
输入两个整数n,m(1<=n,m<1e18)
## 输出
如果先手赢,输出wls,否则输出cocktail
## 输入样例 1
1 1
## 输出样例 1
`wls`
## 输入样例 2
`1 2`
## 输出样例 2
`cocktail`
* * *
## 分析
初级思路——搜索
乍一看,这道题有点像搜索题,也就是一个一个枚举cocktail和wls的棋子,再把(x+1,y+2),(x-1,y+2),(x+1,y-2),(x+1,y-2),(x+2,y-1),(x+2,y+1),(x-2,y+1),(x-2,y-1)这些位置标记掉。
事实上,题目当然不会那么简单。来康康几位同学的结果:
用这样的方法,不是TLE就是RE(还有WA),看来我们急需更简单一些的方法。 更进一步——归纳规律 于是,笔者使用表格模拟棋盘,进行归纳:
(括号)里的数字表示该棋子是第几回合下的; (数字+)表示该回合下的棋同时占用的位置(不是每个马会使8个位置不能下棋吗)。
1×1的时候:
| (1)wls |
1×2的时候:
| (1)wls | (2)cocktail |
1×3的时候:
| (1)wls | (2)cocktail | (3)wls |
2×2的时候:
| (1)wls | (2)cocktail |
| (3)wls | (4)cocktail |
2×3的时候:
| (1)wls | (3)wls | (2)cocktail |
| (2+) | (4)cocktail | (1+) |
3×3的时候:
| (1)wls | (2+) | (5)wls |
| (2+) | (4)cocktail | (1+) |
| (3)wls | (1+) | (2)cocktail |
> warning 注意 > 题目描述里明确规定,“对阵双方都玩得很好”,所以不用考虑下棋顺序的先后,最后所呈现出的棋盘布局和胜负都是唯一的。 列个表归纳总结一下:
| 长×宽 | 1 | 2 | 3 |
| 1 | wls | cocktail | wls |
| 2 | cocktail | cocktail | cocktail |
| 3 | wls | cocktail | wls |
有兴趣的童鞋如果继续列表探索下去的话,就会发现如下规律:
> 当长×宽为偶数时,cocktail总赢; > > 反之,当长×宽为奇数时,wls总赢。
于是简单地给出了代码:
`#include
<bits tdc++.h="">
using namespace std;
long long a,b;
int main(){
cin>>a>>b;
if((a*b)%2==0){
cout<<"cocktail";
}else{
cout<<"wls";
}
return 0;
}`
</bits>
> warning 提示 > 注意数据范围:n,m(1<=n,m<1e18)。 * * *
## 你以为这就结束了?
一提交上去,又WA了。仔细一看上面提示的数据范围:n,m(1<=n,m<1e18)。
试求n×m?1<=n*m<=1e36!这连long long都存不下啊!
于是,只好分别判断两个数的奇偶性了。
## 最终示例代码
#include
<bits tdc++.h="">
using namespace std; long long a,b; int main(){ cin>>a>>b; if(a%2==0||b%2==0){ cout<<"cocktail"; }else{ cout<<"wls"; } return 0; }
</bits>