시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB180402629.545%

문제

대한 레슬링 협회는 다가오는 올림픽 선발전을 대비하기 위해 소속 선수들을 두 팀으로 나누려고 한다.

모든 선수는 두 팀 중 하나에 소속되어야 한다. 또, 두 팀에 소속된 선수의 차이는 1을 넘어갈 수 없다. 마지막으로, 각 팀의 몸무게의 합의 차이는 최소가 되어야 한다.

모든 선수들의 몸무게가 주어졌을 때, 위의 조건을 지키면서 팀을 나눈 다음, 각 팀의 몸무게의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선수의 수 n이 주어진다. 다음 n개 줄에는 각 선수의 몸무게가 주어진다. 몸무게는 1보다 크거나 같고, 450보다 작거나 같은 정수이다. 협회에 소속된 선수의 수는 100명을 넘지 않는다.

출력

각 팀의 몸무게의 합을 공백으로 구분해 출력한다. 합이 작은 것을 먼저 출력한다.

예제 입력 1

3
100
90
200

예제 출력 1

190 200
W3sicHJvYmxlbV9pZCI6Ijk0MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWMyYWNcdWI5YzEgXHVkMzAwIFx1YzEyMFx1YmMxYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViMzAwXHVkNTVjIFx1YjgwOFx1YzJhY1x1YjljMSBcdWQ2MTFcdWQ2OGNcdWIyOTQgXHViMmU0XHVhYzAwXHVjNjI0XHViMjk0IFx1YzYyY1x1YjliY1x1ZDUzZCBcdWMxMjBcdWJjMWNcdWM4MDRcdWM3NDQgXHViMzAwXHViZTQ0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMxOGNcdWMxOGQgXHVjMTIwXHVjMjE4XHViNGU0XHVjNzQ0IFx1YjQ1MCBcdWQzMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1YjI5NCBcdWI0NTAgXHVkMzAwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM1ZDAgXHVjMThjXHVjMThkXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVkMzAwXHVjNWQwIFx1YzE4Y1x1YzE4ZFx1YjQxYyBcdWMxMjBcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IDFcdWM3NDQgXHViMTE4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVhYzAxIFx1ZDMwMFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YzEyMFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVkMzAwXHVjNzQ0IFx1YjA5OFx1YjIwOCBcdWIyZTRcdWM3NGMsIFx1YWMwMSBcdWQzMDBcdWM3NTggXHViYWI4XHViYjM0XHVhYzhjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMxMjBcdWMyMThcdWM3NTggXHViYWI4XHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWI4XHViYjM0XHVhYzhjXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgNDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWQ2MTFcdWQ2OGNcdWM1ZDAgXHVjMThjXHVjMThkXHViNDFjIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMyMThcdWIyOTQgMTAwXHViYTg1XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDMwMFx1Yzc1OCBcdWJhYjhcdWJiMzRcdWFjOGNcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQ1NjlcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWJhM2NcdWM4MDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiA8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5NDIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV3Jlc3RsaW5nIFRlYW1zIFNlbGVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIFRoYWkgV3Jlc3RsaW5nIEFzc29jaWF0aW9uIG11c3QgZGl2aWRlIGl0cyBtZW1iZXJzIGludG8gdHdvIHRlYW1zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHBlcnNvbiBtdXN0IGJlIG9uIG9uZSB0ZWFtIG9yIHRoZSBvdGhlcjsgdGhlIG51bWJlciBvZiBwZW9wbGUgb24gdGhlIHR3byB0ZWFtcyBtdXN0IG5vdCBkaWZmZXIgYnkgbW9yZSB0aGFuIDE7IHRoZSB0b3RhbCB3ZWlnaHQgb2YgdGhlIHBlb3BsZSBvbiBlYWNoIHRlYW0gc2hvdWxkIGJlIGFzIG5lYXJseSBlcXVhbCBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG4gdGhlIG51bWJlciBvZiBwZW9wbGUgaW4gdGhlIGFzc29jaWF0aW9uLCBhbmQgbiBsaW5lcyBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIGdpdmVzIHRoZSB3ZWlnaHQgb2YgcGVyc29uIDE7IHRoZSBzZWNvbmQgdGhlIHdlaWdodCBvZiBwZXJzb24gMjsgYW5kIHNvIG9uLiBFYWNoIHdlaWdodCBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgNDUwLiBUaGVyZSBhcmUgYXQgbW9zdCAxMDAgcGVvcGxlIGluIHRoZSBhc3NvY2lhdGlvbi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIG91dHB1dCB3aWxsIGJlIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyAyIG51bWJlcnM6IHRoZSB0b3RhbCB3ZWlnaHQgb2YgdGhlIHBlb3BsZSBvbiBvbmUgdGVhbSwgYW5kIHRoZSB0b3RhbCB3ZWlnaHQgb2YgdGhlIHBlb3BsZSBvbiB0aGUgb3RoZXIgdGVhbS4gSWYgdGhlc2UgbnVtYmVycyBkaWZmZXIsIGdpdmUgdGhlIHNtYWxsZXIgZmlyc3QuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Thailand > Asia Thailand National Programming Contest > 2009 ACM-ICPC Thailand National Programming Contest F번