题目描述
"Duel!"
Betting on the lovely princess Claris, the duel between Tokitsukaze and Quailty has started.
There are $ n $ cards in a row. Each card has two sides, one of which has color. At first, some of these cards are with color sides facing up and others are with color sides facing down. Then they take turns flipping cards, in which Tokitsukaze moves first. In each move, one should choose exactly $ k $ consecutive cards and flip them to the same side, which means to make their color sides all face up or all face down. If all the color sides of these $ n $ cards face the same direction after one's move, the one who takes this move will win.
Princess Claris wants to know who will win the game if Tokitsukaze and Quailty are so clever that they won't make mistakes.
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 10^5 $ ).
The second line contains a single string of length $ n $ that only consists of $ 0 $ and $ 1 $ , representing the situation of these $ n $ cards, where the color side of the $ i $ -th card faces up if the $ i $ -th character is $ 1 $ , or otherwise, it faces down and the $ i $ -th character is $ 0 $ .
输出格式
Print "once again" (without quotes) if the total number of their moves can exceed $ 10^9 $ , which is considered a draw.
In other cases, print "tokitsukaze" (without quotes) if Tokitsukaze will win, or "quailty" (without quotes) if Quailty will win.
Note that the output characters are case-sensitive, and any wrong spelling would be rejected.
样例 #1
样例输入 #1
4 2
0101
样例输出 #1
quailty
样例 #2
样例输入 #2
6 1
010101
样例输出 #2
once again
样例 #3
样例输入 #3
6 5
010101
样例输出 #3
tokitsukaze
样例 #4
样例输入 #4
4 1
0011
样例输出 #4
once again
提示
In the first example, no matter how Tokitsukaze moves, there would be three cards with color sides facing the same direction after her move, and Quailty can flip the last card to this direction and win.
In the second example, no matter how Tokitsukaze moves, Quailty can choose the same card and flip back to the initial situation, which can allow the game to end in a draw.
In the third example, Tokitsukaze can win by flipping the leftmost five cards up or flipping the rightmost five cards down.
The fourth example can be explained in the same way as the second example does.
首先发现，如果第一次先手没有获胜，那么后手至少不会输。后手可以重复先手操作，等到最后一操作就获胜的时候操作。先手也是这样，如果他第一次操作完后手不能获胜，那么他可以重复后手操作。也就是说，他们要不玩无限轮，要不只玩两轮。
先手是否能获胜，取决于是否可以一次操作覆盖完所有的 0 或 1.那么可以找到 \(0\) 的最小最大坐标和 \(1\) 的最小最大坐标，然后操作即可。
但是如何判断后手是否有可能在先手操作完立刻获胜呢？如果 \(2k<n\)，那么操作区间特别大，后手覆盖不完。同时存在一个区间 \([l,l+k-1]\) 不满足 \(s_1=s_2=\cdots s_{l-1}\) 或 \(s_{l+k}=s_{l+k+1}=\cdots s_{n}\)，那么后手不可能同时覆盖两个区间，所以后手不能胜。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,f[N],mx1,mn1,mx0,mn0,g[N];
char str[N];
int main()
{
scanf("%d%d%s",&n,&k,str+1);
for(int i=2;i<=n;i++)
if(str[i]^str[i-1])
f[0]=1,i=n;
if(!f[0])
{
puts("tokitsukaze");
return 0;
}
f[0]=0;
for(int i=1;i<=n;i++)
{
if(str[i]^'0')
{
if(!mn1)
mn1=i;
mx1=i;
}
else
{
if(!mn0)
mn0=i;
mx0=i;
}
if(i^1)
f[i]=str[i]^str[i-1]||f[i-1];
}
for(int i=n-1;i>=1;i--)
g[i]=g[i+1]||str[i]^str[i+1];
if(mx1-mn1+1<=k||mx0-mn0+1<=k)
{
puts("tokitsukaze");
return 0;
}
for(int i=2;i+k<=n;i++)
{
if(f[i-1]||g[i+k]||k*2<n)
{
puts("once again");
return 0;
}
}
puts("quailty");
return 0;
}