A12698 | Tokitsukaze, CSL and Stone Game
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Tokitsukaze and CSL are playing a little game of stones.
In the beginning, there are $n$ piles of stones, the $i$ -th pile of which has $a_i$ stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?
Consider an example: $n=3$ and sizes of piles are $a_1=2$ , $a_2=3$ , $a_3=0$ . It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be $[1, 3, 0]$ and it is a good move. But if she chooses the second pile then the state will be $[2, 2, 0]$ and she immediately loses. So the only good move for her is to choose the first pile.
Supposing that both players always take their best moves and never make mistakes, who will win the game?
Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.
In the beginning, there are $n$ piles of stones, the $i$ -th pile of which has $a_i$ stones. The two players take turns making moves. Tokitsukaze moves first. On each turn the player chooses a nonempty pile and removes exactly one stone from the pile. A player loses if all of the piles are empty before his turn, or if after removing the stone, two piles (possibly empty) contain the same number of stones. Supposing that both players play optimally, who will win the game?
Consider an example: $n=3$ and sizes of piles are $a_1=2$ , $a_2=3$ , $a_3=0$ . It is impossible to choose the empty pile, so Tokitsukaze has two choices: the first and the second piles. If she chooses the first pile then the state will be $[1, 3, 0]$ and it is a good move. But if she chooses the second pile then the state will be $[2, 2, 0]$ and she immediately loses. So the only good move for her is to choose the first pile.
Supposing that both players always take their best moves and never make mistakes, who will win the game?
Note that even if there are two piles with the same number of stones at the beginning, Tokitsukaze may still be able to make a valid first move. It is only necessary that there are no two piles with the same number of stones after she moves.
输入格式
The first line contains a single integer $n$ ( $1 \le n \le 10^5$ ) — the number of piles.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_1, a_2, \ldots, a_n \le 10^9$ ), which mean the $i$ -th pile has $a_i$ stones.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_1, a_2, \ldots, a_n \le 10^9$ ), which mean the $i$ -th pile has $a_i$ stones.
输出格式
Print "sjfnb" (without quotes) if Tokitsukaze will win, or "cslnb" (without quotes) if CSL will win. Note the output characters are case-sensitive.
输入输出样例
输入 #1
1 0
输出 #1
cslnb
输入 #2
2 1 0
输出 #2
cslnb
输入 #3
2 2 2
输出 #3
sjfnb
输入 #4
3 2 3 1
输出 #4
sjfnb
In the first example, Tokitsukaze cannot take any stone, so CSL will win.
In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.
In the third example, Tokitsukaze will win. Here is one of the optimal ways:
- Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.
- Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.
- Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose.
In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.
In the second example, Tokitsukaze can only take a stone from the first pile, and then, even though they have no stone, these two piles will have the same number of stones, which implies CSL will win.
In the third example, Tokitsukaze will win. Here is one of the optimal ways:
- Firstly, Tokitsukaze can choose the first pile and take a stone from that pile.
- Then, CSL can only choose the first pile, because if he chooses the second pile, he will lose immediately.
- Finally, Tokitsukaze can choose the second pile, and then CSL will have no choice but to lose.
In the fourth example, they only have one good choice at any time, so Tokitsukaze can make the game lasting as long as possible and finally win.
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted