After the big birthday party, Katie still wanted Shiro to have some more fun. Later, she came up with a game called treasure hunt. Of course, she invited her best friends Kuro and Shiro to play with her.
The three friends are very smart so they passed all the challenges very quickly and finally reached the destination. But the treasure can only belong to one cat so they started to think of something which can determine who is worthy of the treasure. Instantly, Kuro came up with some ribbons.
A random colorful ribbon is given to each of the cats. Each color of the ribbon can be represented as an uppercase or lowercase Latin letter. Let's call a consecutive subsequence of colors that appears in the ribbon a subribbon. The beauty of a ribbon is defined as the maximum number of times one of its subribbon appears in the ribbon. The more the subribbon appears, the more beautiful is the ribbon. For example, the ribbon aaaaaaa has the beauty of 7
because its subribbon abc appears twice.
The rules are simple. The game will have n
turns. Every turn, each of the cats must change strictly one color (at one position) in his/her ribbon to an arbitrary color which is different from the unchanged one. For example, a ribbon aaab can be changed into acab in one turn. The one having the most beautiful ribbon after nturns wins the treasure.
Could you find out who is going to be the winner if they all play optimally?
The first line contains an integer n
) — the number of turns.
Next 3 lines contain 3 ribbons of Kuro, Shiro and Katie one per line, respectively. Each ribbon is a string which contains no more than 105
uppercase and lowercase Latin letters and is not empty. It is guaranteed that the length of all ribbons are equal for the purpose of fairness. Note that uppercase and lowercase letters are considered different colors.
Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "Draw".
3 Kuroo Shiro Katie
Kuro
7 treasurehunt threefriends hiCodeforces
Shiro
1 abcabc cbabac ababca
Katie
15 foPaErcvJ mZaxowpbt mkuOlaHRE
Draw
In the first example, after 3
, for example by changing Shiro's ribbon into SSiSS and changing Katie's ribbon into Kaaaa). Therefore, the winner is Kuro.
In the fourth example, since the length of each of the string is 9
and the number of turn is 15, everyone can change their ribbons in some way to reach the maximal beauty of 9 by changing their strings into zzzzzzzzz after 9 turns, and repeatedly change their strings into azzzzzzzz and then into zzzzzzzzz thrice. Therefore, the game ends in a draw.
题目大意为：先输入一个整数n，代表可以改变的次数；
三只猫分别为Kuro,Shiro,Katie;以下三行分别是Kuro,Shiro,Katie所拥有的丝带的颜色，一个字母代表一种颜色，区分大小写；
输出改变之后拥有相同颜色最多的丝带的猫，也是赢家，如果第一名有两只猫或三只猫，则输出‘Draw’
需要注意的是，当n>len（字符串的长度）时，字符串都可以变成一串相同的字母；
当n=1且字符串相同时，此字符串的最大长度应-1（当此字符串的长度不为1时）
代码如下：
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
int n,an,bn,cn,len,maxn,suba,subb,subc;
char a[100005],b[100005],c[100005];
int numa[60],numb[60],numc[60];
while(cin >> n)
{
memset(numa,0,sizeof(numa));
memset(numb,0,sizeof(numa));
memset(numc,0,sizeof(numa));
cin >> a >> b >> c;
len = strlen(a);
//cout << len << endl;
for(int i = 0;i < len;i ++)
{
an = (int)a[i] - 65;
bn = (int)b[i] - 65;
cn = (int)c[i] - 65;
numa[an]++;
numb[bn]++;
numc[cn]++;
}
an = bn = cn = 0;
for(int i = 0;i < 60;i ++)
{
if(an < numa[i])
an = numa[i];
if(bn < numb[i])
bn = numb[i];
if(cn < numc[i])
cn = numc[i];
}
//cout << an << " "<< bn << " "<< cn << endl;
if(an == len && n == 1)
an = len - 1;
else
an = min(an + n,len);
if(bn == len && n == 1)
bn = len - 1;
else
bn = min(bn + n,len);
if(cn == len && n == 1)
cn = len - 1;
else
cn = min(cn + n,len);
//cout << an << " "<< bn << " "<< cn << endl;
if(an > bn && an > cn)
cout << "Kuro" << endl;
else if(bn > an && bn > cn)
cout << "Shiro" << endl;
else if(cn > an && cn > bn)
cout << "Katie" << endl;
else
cout << "Draw" << endl;
}
return 0;
}