시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 150 52 46 43.396%

문제

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

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

상근이는 이 게임을 엄청나게 잘하지만, 희원이는 아직 규칙도 헷갈리는 상황이다. 따라서, 상근이는 희원이를 위해 조금 다르게 게임을 하려고 한다. 상근이는 항상 가장 오른쪽에 있는 종이를 집어간다. 희원이가 이 사실을 알고 있을 때, 희원이가 상근이를 이길 수 있는지 구하고, 만들 수 있는 가장 아름다운 단어를 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

8
cokolada

예제 출력 1

DA
acko
W3sicHJvYmxlbV9pZCI6IjI4NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVjNjQwIFx1YjE4MFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWQxXHVjNWQwXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1NzQgXHVjNjU0XHViMmU0LiBcdWQ1NWMgXHVjODg1XHVjNzc0XHVjNWQwIFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWM1MjkgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YWNlMCwgXHVjNzc0XHViN2VjXHVkNTVjIFx1Yzg4NVx1Yzc3NCBOXHVhYzFjXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YzBhY1x1Yjc4YyBcdWFjMDFcdWFjMDFcdWM3NDAgXHVjNzc0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWJhYThcdWM1NDRcdWMxMWMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgXHVkMTM0XHVjNzQ0IFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWM4ODVcdWM3NzQgXHVkNTVjIFx1YzdhNVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjZTAgXHVjNzkwXHVhZTMwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWI0YTRcdWNhYmRcdWM1ZDAgXHViZDk5XHVjNzc4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWQ1NThcdWFjZTAsIFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVhYzAwXHVjODM4XHVhYzA4IFx1Yzg4NVx1Yzc3NFx1YWMwMCBcdWM1YzZcdWM3M2NcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1Yzg4NVx1YjhjY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YjJlOFx1YzViNCBBXHVjNjQwIEJcdWFjMDAgXHVjNzg4XHVjNzQ0XHViNTRjLCBBXHVhYzAwIEJcdWJjZjRcdWIyZTQgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1YzU1ZVx1YzEyMFx1YjJlNFx1YmE3NCwgQVx1YjI5NCBCXHViY2Y0XHViMmU0IFx1YzU0NFx1Yjk4NFx1YjJmNVx1YjJlNC4gXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDFcdWM3OTAgXHViOWNjXHViNGUwIFx1YjJlOFx1YzViNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHViMzU0IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWIyZThcdWM1YjRcdWI5N2MgXHViOWNjXHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNzc0XHVhZTM0XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNFx1YmE3NCBcdWI0NTggXHViMmU0IFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjNWM0XHVjY2FkXHViMDk4XHVhYzhjIFx1Yzc5OFx1ZDU1OFx1YzljMFx1YjljYywgXHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YzU0NFx1YzljMSBcdWFkZGNcdWNlNTlcdWIzYzQgXHVkNWY3XHVhYzA4XHViOWFjXHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWM4NzBcdWFlMDggXHViMmU0XHViOTc0XHVhYzhjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWM5ZDFcdWM1YjRcdWFjMDRcdWIyZTQuIFx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWFjMDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViOTdjIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YWNlMCwgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWIyZThcdWM1YjRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzlkZFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZTAwXHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCwgXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJnF1b3Q7REEmcXVvdDtcdWI5N2MsIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtORSZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSUdSQSIsImRlc2NyaXB0aW9uIjoiPHA+SGF2aW5nIHNvbHZlZCB0aGUgdGVkaW91cyBhc3NpZ25tZW50LCBNaXJrbyBkZWNpZGVkIHRvIHBsYXkgYSBnYW1lIHdpdGggaGlzIGdvb2QgZnJpZW5kIFNsYXZrby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhleSBoYXZlIHdyaXR0ZW4gYSBzZXF1ZW5jZSBvZiBOIGxldHRlcnMgb24gYSBwaWVjZSBvZiBwYXBlci4gRWFjaCBvbmUgb2YgdGhlbSBpcyB0cnlpbmcgdG8gcHV0IHRvZ2V0aGVyIGEgd29yZCB1c2luZyBsZXR0ZXJzIGZyb20gdGhlIHNlcXVlbmNlLiBUaGV5IGFsdGVybmF0ZSB0YWtpbmcgdHVybnMgY29uc2lzdGluZyBvZiByZW1vdmluZyBhIHNpbmdsZSBsZXR0ZXIgZnJvbSB0aGUgc2VxdWVuY2UgYW5kIGFwcGVuZGluZyBpdCB0byB0aGUgZW5kIG9mIHRoZWlyIHdvcmQuIE1pcmtvIGhhcyB0aGUgZmlyc3QgdHVybi4gVGhlIGdhbWUgZW5kcyB3aGVuIG5vIGxldHRlcnMgYXJlIHJlbWFpbmluZyBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGRlZmluZSBhIHdvcmQgdG8gYmUgbW9yZSBiZWF1dGlmdWwgdGhhbiBhbm90aGVyIHdvcmQgaWYgaXQgY29tZXMgZmlyc3QgYWxwaGFiZXRpY2FsbHkuIFRoZSBwbGF5ZXIgd2hvIGhhcyB0aGUgbW9yZSBiZWF1dGlmdWwgd29yZCBhdCB0aGUgZW5kIG9mIHRoZSBnYW1lIHdpbnMuIElmIGJvdGggcGxheWVycyBoYXZlIGVxdWFsIHdvcmRzLCB0aGV5IGJvdGggbG9zZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaXMgYSBtdWNoIGJldHRlciBwbGF5ZXIgdGhhbiBTbGF2a28sIHNvIGhlIGhhcyBkZWNpZGVkIHRvIG1ha2UgaXQgZWFzaWVyIGZvciBTbGF2a28gYnkgYWx3YXlzIHNlbGVjdGluZyB0aGUgcmlnaHRtb3N0IHJlbWFpbmluZyBsZXR0ZXIgaW4gdGhlIHNlcXVlbmNlLiBLbm93aW5nIHRoaXMsIFNsYXZrbyB3YW50cyB0byBmaW5kIG91dCBpZiBpdCBpcyBwb3NzaWJsZSBmb3IgaGltIHRvIHdpbiBhbmQgd2hpY2ggaXMgdGhlIG1vc3QgYmVhdXRpZnVsIHdvcmQgaGUgY2FuIGVuZCB0aGUgZ2FtZSB3aXRoLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gZXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGNoYXJhY3RlcnMsIHRoZSBzdGFydGluZyBsZXR0ZXIgc2VxdWVuY2UuIEFsbCBjaGFyYWN0ZXJzIGFyZSBsb3dlciBjYXNlIGxldHRlcnMgZnJvbSB0aGUgRW5nbGlzaCBhbHBoYWJldC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluICZsZHF1bztEQSZyZHF1bzsgaWYgaXQgaXMgcG9zc2libGUgZm9yIFNsYXZrbyB0byB3aW4sIGFuZCAmbGRxdW87TkUmcmRxdW87IG90aGVyd2lzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1vc3QgYmVhdXRpZnVsIHdvcmQgdGhhdCBTbGF2a28gY2FuIGhhdmUgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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