시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 73 22 20 38.462%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

8
cokolada

예제 출력

DA
acko

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 3번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: myungwoo