2871번

수정 전

시간 제한 메모리 제한
1 초 128 MB

문제

상근이는 희원이와 놀기 위해 집에서 게임을 준비해 왔다. 먼저, 한 종이에 한 글자씩 써 있고, 이러한 종이가 총 N장 있다. 그리고, 이 종이를 모두 하나로 모아서 단어를 만든다. 그 다음에 턴을 번갈아가면서 단어에서 종이 한 장을 가져가고 자기 단어의 뒤쪽에 붙인다. 상근이가 게임을 먼저하고, 더 이상 가져갈 종이가 없으면 게임을 종료한다.
 
두 단어 A와 B가 있을때, A가 B보다 사전순으로 앞선다면, A는 B보다 아름답다. 두 플레이어가 각자 만든 단어 중에서 더 아름다운 단어를 만든 사람이 게임을 이긴다. 만약, 두 사람이 같은 단어를 만들었다면, 둘 다 지는 경우다.
 
상근이는 이 게임을 엄청나게 잘하지만, 희원이는 아직 규칙도 헷갈리는 상황이다. 따라서, 상근이는 희원이를 위해 조금 다른 규칙을 만들어주었다. 희원이는 항상 단어의 가장 오른쪽에 있는 종이를 집어간다.
 
위와 같이 상근이가 자신을 위해서 바꿔준 규칙으로 희원이가 게임했을 때, 상근이를 이길 수 있는지 구하고, 만들 수 있는 가장 아름다운 단어를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 짝수 N이 주어진다. (2 ≤ N ≤ 100 000)
 
둘재 줄에 종이에 적혀져있는 글자가 순서대로 주어진다. 글자는 모두 알파벳 소문자로만 이루어져 있따.

출력

만약, 희원이가 이길 수 있다면 첫째 줄에 "DA"를, 없다면 "NE"를 출력한다. 둘째 줄에는 희원이가 만들 수 있는 가장 아름다운 단어를 출력한다.

예제 입력

8 cokolada

예제 출력

DA acko

힌트

수정 후

시간 제한 메모리 제한
1 초 128 MB

문제

상근이는 희원이와 놀기 위해 집에서 게임을 준비해 왔다. 먼저, 한 종이에 한 글자씩 써 있고, 이러한 종이가 총 N장 있다. 그리고, 이 종이를 모두 하나로 모아서 단어를 만든다. 그 다음에 턴을 번갈아가면서 단어에서 종이 한 장을 가져가고 자기 단어의 뒤쪽에 붙인다. 상근이가 게임을 먼저하고, 더 이상 가져갈 종이가 없으면 게임을 종료한다.

두 단어 A와 B가 있을때, A가 B보다 사전순으로 앞선다면, A는 B보다 아름답다. 두 플레이어가 각자 만든 단어 중에서 더 아름다운 단어를 만든 사람이 게임을 이긴다. 만약, 두 사람이 같은 단어를 만들었다면, 둘 다 지는 경우다.

상근이는 이 게임을 엄청나게 잘하지만, 희원이는 아직 규칙도 헷갈리는 상황이다. 따라서, 상근이는 희원이를 위해 조금 다른게 게임을 하려고 한다. 상근이는 항상 단어의 가장 오른쪽에 있는 종이를 집어간다.

위와 같이 상근이가 항상 오른쪽에 있는 종이만 집어갈 때, 희원이가 상근이를 이길 수 있는지 구하고, 만들 수 있는 가장 아름다운 단어를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 짝수 N이 주어진다. (2 ≤ N ≤ 100 000)

둘재 줄에 종이에 적혀져있는 글자가 순서대로 주어진다. 글자는 모두 알파벳 소문자로만 이루어져 있따.

출력

만약, 희원이가 이길 수 있다면 첫째 줄에 "DA"를, 없다면 "NE"를 출력한다. 둘째 줄에는 희원이가 만들 수 있는 가장 아름다운 단어를 출력한다.

예제 입력

8 cokolada

예제 출력

DA acko

힌트