CF1190B.Tokitsukaze, CSL and Stone Game
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ai 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 a1=2, a2=3, a3=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.
Tokitsukaze 和 CSL 正在玩一个关于石子的小游戏。
游戏开始时,共有 n 堆石子,其中第 i 堆有 ai 颗石子。两名玩家轮流进行操作,Tokitsukaze 先手。每次操作中,当前玩家需选择一个非空石子堆,并从中恰好移除一颗石子。若轮到某玩家操作时所有石子堆均已为空,或该玩家移除一颗石子后存在两堆(可能为空)石子数量相同,则该玩家判负。假设双方均以最优策略进行游戏,问最终谁将获胜?
考虑一个例子:n=3,各堆石子数为 a1=2,a2=3,a3=0。由于不能选择空堆,Tokitsukaze 仅有两个可选操作:对第一堆或第二堆操作。若她选择第一堆,则局面变为 [1,3,0],这是一个合法操作;但若她选择第二堆,则局面变为 [2,2,0],此时存在两堆石子数相同,她立即落败。因此,她唯一合法的操作是选择第一堆。
假设双方始终采取最优策略且永不失误,问最终谁将获胜?
注意:即使初始时已有两堆石子数量相同,Tokitsukaze 仍可能作出一个合法的首步操作——只要她在移除一颗石子后,不再存在任意两堆石子数量相同即可。
输入格式
The first line contains a single integer n (1≤n≤105) — the number of piles.
The second line contains n integers a1,a2,…,an (0≤a1,a2,…,an≤109), which mean the i-th pile has ai stones.
第一行包含一个整数 n(1≤n≤105)—— 表示石堆的数量。
第二行包含 n 个整数 a1,a2,…,an(0≤a1,a2,…,an≤109),其中 ai 表示第 i 堆石子的数量。
输出格式
Print "sjfnb" (without quotes) if Tokitsukaze will win, or "cslnb" (without quotes) if CSL will win. Note the output characters are case-sensitive.
如果时雨酱获胜,则输出 "sjfnb"(不含引号);如果 CSL 获胜,则输出 "cslnb"(不含引号)。注意输出的字符区分大小写。
输入输出样例
输入#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.
在第一个例子中,时雨无法取走任何石子,因此CSL获胜。
在第二个例子中,时雨只能从第一堆石子中取走一颗石子;此后,尽管这两堆石子数量均为零,但它们的数量相等,这意味着CSL获胜。
在第三个例子中,时雨获胜。以下是一种最优策略:
- 首先,时雨可以选择第一堆石子并从中取走一颗石子。
- 接着,CSL只能选择第一堆石子,因为如果他选择第二堆石子,将立即失败。
- 最后,时雨可以选择第二堆石子,此时CSL将别无选择,只能失败。
在第四个例子中,他们在任意时刻都只有一种合法的选择,因此时雨可以使游戏尽可能延长,并最终获胜。
输入解题思路,AI测评打分。不知道怎么写?