시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 113 42 38 45.238%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1

8
cokolada

예제 출력 1

DA
acko
W3sicHJvYmxlbV9pZCI6IjI4NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVjNjQwIFx1YjE4MFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWQxXHVjNWQwXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1NzQgXHVjNjU0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1ZDU1YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVkNTVjIFx1YWUwMFx1Yzc5MFx1YzUyOSBcdWMzNjggXHVjNzg4XHVhY2UwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODg1XHVjNzc0XHVhYzAwIFx1Y2QxZCBOXHVjNzc0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWM3NzQgXHVjODg1XHVjNzc0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWQ1NThcdWIwOThcdWI4NWMgXHViYWE4XHVjNTQ0XHVjMTFjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVkMTM0XHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWIyZThcdWM1YjRcdWM1ZDBcdWMxMWMgXHVjODg1XHVjNzc0IFx1ZDU1YyBcdWM3YTVcdWM3NDQgXHVhYzAwXHVjODM4XHVhYzAwXHVhY2UwIFx1Yzc5MFx1YWUzMCBcdWIyZThcdWM1YjRcdWM3NTggXHViNGE0XHVjYWJkXHVjNWQwIFx1YmQ5OVx1Yzc3OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWJhM2NcdWM4MDBcdWQ1NThcdWFjZTAsIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVhYzAwXHVjODM4XHVhYzA4IFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWM1YzZcdWM3M2NcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjJlOFx1YzViNCBBXHVjNjQwIEJcdWFjMDAgXHVjNzg4XHVjNzQ0XHViNTRjLCBBXHVhYzAwIEJcdWJjZjRcdWIyZTQgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzEyMFx1YjJlNFx1YmE3NCwgQVx1YjI5NCBCXHViY2Y0XHViMmU0IFx1YzU0NFx1Yjk4NFx1YjJmNVx1YjJlNC4gXHViNDUwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWFjMDFcdWM3OTAgXHViOWNjXHViNGUwIFx1YjJlOFx1YzViNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHViMzU0IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWIyZThcdWM1YjRcdWI5N2MgXHViOWNjXHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM0XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTRcdWJhNzQsIFx1YjQ1OCBcdWIyZTQgXHVjOWMwXHViMjk0IFx1YWNiZFx1YzZiMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1Yzc5OFx1ZDU1OFx1YzljMFx1YjljYywgXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YzU0NFx1YzljMSBcdWFkZGNcdWNlNTlcdWIzYzQgXHVkNWY3XHVhYzA4XHViOWFjXHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWM4NzBcdWFlMDggXHViMmU0XHViOTc4XHVhYzhjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4ODVcdWM3NzRcdWI5N2MgXHVjOWQxXHVjNWI0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ1NmRcdWMwYzEgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM4ODVcdWM3NzRcdWI5Y2MgXHVjOWQxXHVjNWI0XHVhYzA4IFx1YjU0YywmbmJzcDtcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YWNlMCwgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWIyZThcdWM1YjRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzlkZFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjN2FjIFx1YzkwNFx1YzVkMCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjODM4XHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFlMDBcdWM3OTBcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5Y2NcdWM1N2QsIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwICZxdW90O0RBJnF1b3Q7XHViOTdjLCBcdWM1YzZcdWIyZTRcdWJhNzQgJnF1b3Q7TkUmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklHUkEiLCJkZXNjcmlwdGlvbiI6IjxwPkhhdmluZyBzb2x2ZWQgdGhlIHRlZGlvdXMgYXNzaWdubWVudCwgTWlya28gZGVjaWRlZCB0byBwbGF5IGEgZ2FtZSB3aXRoIGhpcyBnb29kIGZyaWVuZCBTbGF2a28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXkgaGF2ZSB3cml0dGVuIGEgc2VxdWVuY2Ugb2YgTiBsZXR0ZXJzIG9uIGEgcGllY2Ugb2YgcGFwZXIuIEVhY2ggb25lIG9mIHRoZW0gaXMgdHJ5aW5nIHRvIHB1dCB0b2dldGhlciBhIHdvcmQgdXNpbmcgbGV0dGVycyBmcm9tIHRoZSBzZXF1ZW5jZS4gVGhleSBhbHRlcm5hdGUgdGFraW5nIHR1cm5zIGNvbnNpc3Rpbmcgb2YgcmVtb3ZpbmcgYSBzaW5nbGUgbGV0dGVyIGZyb20gdGhlIHNlcXVlbmNlIGFuZCBhcHBlbmRpbmcgaXQgdG8gdGhlIGVuZCBvZiB0aGVpciB3b3JkLiBNaXJrbyBoYXMgdGhlIGZpcnN0IHR1cm4uIFRoZSBnYW1lIGVuZHMgd2hlbiBubyBsZXR0ZXJzIGFyZSByZW1haW5pbmcgaW4gdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XZSBkZWZpbmUgYSB3b3JkIHRvIGJlIG1vcmUgYmVhdXRpZnVsIHRoYW4gYW5vdGhlciB3b3JkIGlmIGl0IGNvbWVzIGZpcnN0IGFscGhhYmV0aWNhbGx5LiBUaGUgcGxheWVyIHdobyBoYXMgdGhlIG1vcmUgYmVhdXRpZnVsIHdvcmQgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZSB3aW5zLiBJZiBib3RoIHBsYXllcnMgaGF2ZSBlcXVhbCB3b3JkcywgdGhleSBib3RoIGxvc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGEgbXVjaCBiZXR0ZXIgcGxheWVyIHRoYW4gU2xhdmtvLCBzbyBoZSBoYXMgZGVjaWRlZCB0byBtYWtlIGl0IGVhc2llciBmb3IgU2xhdmtvIGJ5IGFsd2F5cyBzZWxlY3RpbmcgdGhlIHJpZ2h0bW9zdCByZW1haW5pbmcgbGV0dGVyIGluIHRoZSBzZXF1ZW5jZS4gS25vd2luZyB0aGlzLCBTbGF2a28gd2FudHMgdG8gZmluZCBvdXQgaWYgaXQgaXMgcG9zc2libGUgZm9yIGhpbSB0byB3aW4gYW5kIHdoaWNoIGlzIHRoZSBtb3N0IGJlYXV0aWZ1bCB3b3JkIGhlIGNhbiBlbmQgdGhlIGdhbWUgd2l0aC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGV2ZW4gcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMCAwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBjaGFyYWN0ZXJzLCB0aGUgc3RhcnRpbmcgbGV0dGVyIHNlcXVlbmNlLiBBbGwgY2hhcmFjdGVycyBhcmUgbG93ZXIgY2FzZSBsZXR0ZXJzIGZyb20gdGhlIEVuZ2xpc2ggYWxwaGFiZXQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiAmbGRxdW87REEmcmRxdW87IGlmIGl0IGlzIHBvc3NpYmxlIGZvciBTbGF2a28gdG8gd2luLCBhbmQgJmxkcXVvO05FJnJkcXVvOyBvdGhlcndpc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtb3N0IGJlYXV0aWZ1bCB3b3JkIHRoYXQgU2xhdmtvIGNhbiBoYXZlIGF0IHRoZSBlbmQgb2YgdGhlIGdhbWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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