Treasure Hunt CodeForces - 979B

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?77?because its subribbon?a?appears?77times,and the ribbon?abcdabc?has the beauty of?22?because its subribbon?abc?appears twice.

The rules are simple. The game will have?nn?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?nnturns wins the treasure.

Could you find out who is going to be the winner if they all play optimally?

Input

The first line contains an integer?nn?(0≤n≤1090≤n≤109)?— 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?105105?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.

Output

Print the name of the winner ("Kuro","Shiro" or "Katie"). If there are at least two cats that share the maximum beauty,print "Draw".

Examples

3
Kuroo
Shiro
Katie

Kuro

7
treasurehunt
threefriends
hiCodeforces

Shiro

1
abcabc
cbabac
ababca

Katie

15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

Draw

Note

In the first example,after?33?turns,Kuro can change his ribbon into?ooooo,which has the beauty of?55,while reaching such beauty for Shiro and Katie is impossible (both Shiro and Katie can reach the beauty of at most?44,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?99?and the number of turn is?1515,everyone can change their ribbons in some way to reach the maximal beauty of?99?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.

?

原题链接：http://codeforces.com/problemset/problem/979/B

题目大意：

? ? 贪心。

? ? 三个人玩游戏，有三个等长字符串，每个人每次可以更改自己字符串中的一个字母，给出可修改次数n，求问最后哪个人的字符串里，重复最多的子串最多，如果有并列第一第二（第三）的情况就平局。

? ? 一个串重复次数=这个串里每个字母的重复次数，所以最优是选单个字母重复最多（贪心）。

?

　　首先统计串中出现次数最多的字母计数num：

　　1??若num+n大于字符串长度len，则beauty=len；

　　2??若num+n小于等于len，则beauty=num+n；

　　3??特殊情况，若val==len，“aaaaaaaa”，且n==1，最后必然会有一个a变成别的字母，“baaaaaaa”。

????? 即若val==len && n==1 beauty=val--。

? ? ? 有一个样例n=3，aaaaa aaaaa aaaab 结果是draw。如果理解就没问题啦。

?

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstdlib>  
 4 #include<cstring>  
 5 #include<cmath>  
 6 #include<string>  
 7 #include<algorithm>  
 8 #include<vector>  
 9 #include<queue>  
10 #include<set>  
11 #include<map>  
12 #include<stack>  
13 using namespace std;
14 const int inf = 0x3f3f3f3f;
15 
16 
17 
18 int n;
19 int len;
20 int max1,max2,max3;
21 void print()
22 {
23     if (max1>max2&&max1>max3)
24     {
25         cout << "Kuro" << endl;
26     }
27     else if (max2>max1&&max2>max3)
28     {
29         cout << "Shiro" << endl;
30     }
31     else if (max3>max1&&max3>max2)
32     {
33         cout << "Katie" << endl;
34     }
35     else
36         cout << "Draw" << endl;
37 }
38 int work()
39 {
40     char s[200005];
41     int cnt[300];
42     memset(cnt,0,sizeof(cnt));
43     int ans = -1;
44     scanf("%s",s);
45     int len = strlen(s);
46     for (int i = 0; i<len; i++)
47     {
48         cnt[s[i]]++;
49         ans = max(ans,cnt[s[i]]);
50     }
51     if (ans == len&&n == 1)
52         return len - 1;
53     else if (len - ans >= n)
54         return ans + n;
55     else
56         return len;
57 }
58 int main()
59 {
60     scanf("%d",&n);
61     max1 = work();
62     max2 = work();
63     max3 = work();
64     print();
65     getchar();
66     getchar();
67 }