小小马
## 描述
鸡尾酒是小小马的粉丝,于是他比较喜欢研究关于“马”的问题。
给你一个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>