Informatica Online Judge

  아름다운 구슬열 [2292 / 08F4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 22   Total Tried : 17


The Champion of this Problem (C++) : gs15120 - 0ms / 567byte
My Best Submission (C++) : N/A

[Codeforces 979]

Background

경곽이, 영재, 정보 이렇게 3명은 매우 머리가 좋은 친구들이다.

이 친구들이 재미 있는 색깔 구슬 게임을 하려고 한다.

색깔 구슬 게임은 각각 길이가 같은 구슬열을 가지고 시작한다.

구슬열을 구성하는 각 구슬들은 다양한 색깔을 가진다.

각 색깔은 하나의 알파벳으로 표현된다. 여기서 알파벳은 대, 소문자를 모두 사용한다.

3명의 친구들은 이 구슬열을 최대한 아름답도록 하려고 한다.

구슬열의 아름다움은 구슬열을 구성하는 모든 sub-string들 중 가장 많이 등장하는 sub-string의 수로 결정된다.

예를 들어 "$abcdabc$"라는 구슬열을 가지고 있다면 이 구슬열의 아름다움은 $2$이다.

이는 "$abc$"라는 sub-string이 $2$번 등장하고 $3$번 이상 등장하는 sub-string가 없기 때문이다.

다른 예로 "$aaa$"라는 구슬열의 아름다움은 $3$이다. "$a$"라는 sub-string이 $3$번 등장하기 때문이다.

3명의 친구들이 각각 자신의 구슬열의 구슬들 중 정확하게 $n$개의 색깔을 다른 색깔로 변경하여 아름다움의 값을 갱신하고자 한다.

3명의 친구들이 각각 자신의 구슬열의 아름다움을 최대로 하기 위해서 최선을 다한다.

이 게임의 승자는 최고의 아름다움 값을 가진 자가 승리한다.

만약 2명 이상이 같은 값으로 최고의 아룸다움을 가지게 되면 승자는 없다. 즉, 승자는 유일해야 한다.

구슬의 색깔을 변경해야 하는 값 $n$과 각각의 구슬열이 주어질 때, 모두 최선을 다한다면 누가 우승하는지를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 변경해야하는 구슬의 개수를 나타내는 자연수 $n$이 주어진다.

두 번째 줄부터 3줄에 걸쳐서 각각 경곽이, 영재, 정보의 구슬열이 한 줄에 하나씩 주어진다.

[입력값의 정의역]

$0 ≤ n ≤ 1,000,000,000$

$구슬열의 최대 길이 ≤ 100,000$

구슬열을 구성하는 문자는 알파벳 대, 소문자로만 구성된다.

Output

경곽이가 우승하면 "K", 영재가 우승하면 "Y", 정보가 우승하면 "J", 우승자를 결정할 수 없다면 "Draw"를 출력한다. (단, 따옴표는 제외)

IO Example

입력
3
abczz
young
pdort

출력
K

* 설명 : 모두 3개씩 바꿔야 하므로 경곽이는 zzzzz로 바꿀 수 있다. 이경우 아름다움은 5가되면 다른 친구들보다 더 아름다운 구슬열이 되어 우승하게 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]