시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 4 4 22.222%

문제

민혁이와 민규는 보석으로 가득찬 박스를 가지고 있고, 이제 이 보석을 나누려고 한다. 하지만, 각 보석의 가치가 다르기 때문에 공정하게 보석을 나누는 것은 매우 어려운 일이다.

보석을 나누기 위해서, 턴을 번갈아가면서 보석을 하나씩 가져간다. 보석이 남아있지 않을 때 까지 턴을 번갈아가며, 누가 먼저 시작할지는 동전을 던져서 결정한다.

민혁이와 민규는 서로 다른 전략을 가지고 보석을 고르려고 한다. 민혁이는 남아있는 보석 중에서 민혁이에게 가장 가치있는 보석을 고른다. 만약, 그러한 보석이 여러가지라면, 민규에게 가장 가치가 없는 보석을 고른다.

민규는 최종 가치의 합이 최대가 되게 보석을 고른다. 만약, 그러한 보석이 여러가지라면, 민혁이의 최종 가치가 최대한 크게 되는 보석을 고른다.

누가 턴을 먼저 시작할지와, 각 사람이 느끼는 보석의 가치가 주어졌을 때, 두 사람이 가져가는 보석의 가치를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (T ≤ 100)가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

  • 보석의 개수 n (1 ≤ n ≤ 1000)
  • 먼저 턴을 시작하는 사람의 이름 (민혁이인 경우에는 "Petra", 민규인 경우에는 "Jan")
  • n개의 줄에 걸쳐서 민혁이가 느끼는 가치 pi, 민규가 느끼는 가치 ji (0 ≤ pi, ji ≤ 1 000)

출력

각 테스트 케이스에 대해서 두 사람이 최종적으로 가져가는 보석 가치를 출력한다.

예제 입력 1

3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4

예제 출력 1

170 130
14 16
9 10
W3sicHJvYmxlbV9pZCI6IjM2NjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZjRcdWMxMWQgXHViZDg0XHViYzMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWM2NDAgXHViYmZjXHVhZGRjXHViMjk0IFx1YmNmNFx1YzExZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWI0ZGRcdWNjMmMgXHViYzE1XHVjMmE0XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1Yzc3NFx1YzgxYyBcdWM3NzQgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzAxIFx1YmNmNFx1YzExZFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHViMmU0XHViOTc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjZjVcdWM4MTVcdWQ1NThcdWFjOGMgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YjA5OFx1YjIwNFx1YjI5NCBcdWFjODNcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzViNFx1YjgyNFx1YzZiNCBcdWM3N2NcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1YzExZFx1Yzc0NCBcdWIwOThcdWIyMDRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWQxMzRcdWM3NDQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YmNmNFx1YzExZFx1Yzc0NCBcdWQ1NThcdWIwOThcdWM1MjkgXHVhYzAwXHVjODM4XHVhYzA0XHViMmU0LiBcdWJjZjRcdWMxMWRcdWM3NzQgXHViMGE4XHVjNTQ0XHVjNzg4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWI1NGMgXHVhZTRjXHVjOWMwIFx1ZDEzNFx1Yzc0NCBcdWJjODhcdWFjMDhcdWM1NDRcdWFjMDBcdWJhNzAsIFx1YjIwNFx1YWMwMCBcdWJhM2NcdWM4MDAgXHVjMmRjXHVjNzkxXHVkNTYwXHVjOWMwXHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc0NCBcdWIzNThcdWM4MzhcdWMxMWMgXHVhY2IwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWM2NDAgXHViYmZjXHVhZGRjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODA0XHViN2I1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhY2UwXHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVjZTU4XHVjNzg4XHViMjk0IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YmNmNFx1YzExZFx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YmJmY1x1YWRkY1x1YzVkMFx1YWM4YyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVjZTU4XHVhYzAwIFx1YzVjNlx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhY2UwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiZmNcdWFkZGNcdWIyOTQgXHVjZDVjXHVjODg1IFx1YWMwMFx1Y2U1OFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHViMzAwXHVhYzAwIFx1YjQxOFx1YWM4YyBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhY2UwXHViOTc4XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWJjZjRcdWMxMWRcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWJiZmNcdWQ2MDFcdWM3NzRcdWM3NTggXHVjZDVjXHVjODg1IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVkMDZjXHVhYzhjIFx1YjQxOFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhY2UwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyMDRcdWFjMDAgXHVkMTM0XHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NjBcdWM5YzBcdWM2NDAsIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMjkwXHViMDdjXHViMjk0IFx1YmNmNFx1YzExZFx1Yzc1OCBcdWFjMDBcdWNlNThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzU4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViY2Y0XHVjMTFkXHVjNzU4IFx1YWMxY1x1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEwMDApPFwvbGk+XHJcblx0PGxpPlx1YmEzY1x1YzgwMCBcdWQxMzRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWM3NzRcdWI5ODQgKFx1YmJmY1x1ZDYwMVx1Yzc3NFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7UGV0cmEmcXVvdDssIFx1YmJmY1x1YWRkY1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7SmFuJnF1b3Q7KTxcL2xpPlxyXG5cdDxsaT5uXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViYmZjXHVkNjAxXHVjNzc0XHVhYzAwIFx1YjI5MFx1YjA3Y1x1YjI5NCBcdWFjMDBcdWNlNTggcDxzdWI+aTxcL3N1Yj4sIFx1YmJmY1x1YWRkY1x1YWMwMCBcdWIyOTBcdWIwN2NcdWIyOTQgXHVhYzAwXHVjZTU4IGo8c3ViPmk8XC9zdWI+ICgwICZsZTsgcDxzdWI+aTxcL3N1Yj4sIGo8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAxIDAwMCk8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2Q1Y1x1Yzg4NVx1YzgwMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWIyOTQgXHViY2Y0XHVjMTFkIFx1YWMwMFx1Y2U1OFx1Yjk3YyZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnJlZSBHb29kaWVzIiwiZGVzY3JpcHRpb24iOiI8cD5QZXRyYSBhbmQgSmFuIGhhdmUganVzdCByZWNlaXZlZCBhIGJveCBmdWxsIG9mIGZyZWUgZ29vZGllcywgYW5kIHdhbnQgdG8gZGl2aWRlIHRoZSBnb29kaWVzIGJldHdlZW4gdGhlbS4gSG93ZXZlciwgaXQgaXMgbm90IGVhc3kgdG8gZG8gdGhpcyBmYWlybHksIHNpbmNlIHRoZXkgYm90aCB2YWx1ZSBkaWZmZXJlbnQgZ29vZGllcyBkaWZmZXJlbnRseS48XC9wPlxyXG5cclxuPHA+VG8gZGl2aWRlIHRoZSBnb29kaWVzLCB0aGV5IGhhdmUgZGVjaWRlZCB1cG9uIHRoZSBmb2xsb3dpbmcgcHJvY2VkdXJlOiB0aGV5IGNob29zZSBnb29kaWVzIG9uZSBieSBvbmUsIGluIHR1cm4sIHVudGlsIGFsbCB0aGUgZ29vZGllcyBhcmUgY2hvc2VuLiBBIGNvaW4gaXMgdG9zc2VkIHRvIGRlY2lkZSB3aG8gZ2V0cyB0byBjaG9vc2UgdGhlIGZpcnN0IGdvb2RpZS48XC9wPlxyXG5cclxuPHA+UGV0cmEgYW5kIEphbiBoYXZlIGRpZmZlcmVudCBzdHJhdGVnaWVzIGluIGRlY2lkaW5nIHdoYXQgdG8gY2hvb3NlLiBXaGVuIGZhY2VkIHdpdGggYSBjaG9pY2UsIFBldHJhIGFsd2F5cyBzZWxlY3RzIHRoZSBnb29kaWUgdGhhdCBpcyBtb3N0IHZhbHVhYmxlIHRvIGhlci4gSW4gY2FzZSBvZiBhIHRpZSwgc2hlIGlzIHZlcnkgY29uc2lkZXJhdGUgYW5kIHBpY2tzIHRoZSBvbmUgdGhhdCBpcyBsZWFzdCB2YWx1YWJsZSB0byBKYW4uIChTaW5jZSBQZXRyYSBhbmQgSmFuIGFyZSBnb29kIGZyaWVuZHMsIHRoZXkga25vdyBleGFjdGx5IGhvdyBtdWNoIHZhbHVlIHRoZSBvdGhlciBwbGFjZXMgb24gZWFjaCBnb29kaWUuKTxcL3A+XHJcblxyXG48cD5KYW4mcnNxdW87cyBzdHJhdGVneSwgaG93ZXZlciwgY29uc2lzdHMgb2YgbWF4aW1pemluZyBoaXMgb3duIGZpbmFsIHZhbHVlLiBIZSBpcyBhbHNvIHZlcnkgY29uc2lkZXJhdGUsIHNvIGlmIG11bHRpcGxlIGNob2ljZXMgbGVhZCB0byB0aGUgc2FtZSBvcHRpbWFsIHJlc3VsdCwgaGUgcHJlZmVycyBQZXRyYSB0byBoYXZlIGFzIG11Y2ggZmluYWwgdmFsdWUgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHJlc3VsdCBvZiB0aGUgaW5pdGlhbCBjb2luIHRvc3MuIEFmdGVyIEphbiBhbmQgUGV0cmEgaGF2ZSBmaW5pc2hlZCBkaXZpZGluZyBhbGwgdGhlIGdvb2RpZXMgYmV0d2VlbiB0aGVtc2VsdmVzLCB3aGF0IGlzIHRoZSB0b3RhbCB2YWx1ZSBvZiB0aGUgZ29vZGllcyBlYWNoIG9mIHRoZW0gZW5kcyB1cCB3aXRoPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgYSBwb3NpdGl2ZSBpbnRlZ2VyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMSAwMDApOiB0aGUgbnVtYmVyIG9mIGdvb2RpZXMuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYSBzdHJpbmcsIGVpdGhlciAmbGRxdW87UGV0cmEmcmRxdW87IG9yICZsZHF1bztKYW4mcmRxdW87OiB0aGUgcGVyc29uIHRoYXQgY2hvb3NlcyBmaXJzdC48XC9saT5cclxuXHQ8bGk+biBsaW5lcyB3aXRoIHR3byBpbnRlZ2VycyBwPHN1Yj5pPFwvc3ViPiBhbmQgajxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBwPHN1Yj5pPFwvc3ViPiwgajxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCkgZWFjaDogdGhlIHZhbHVlcyB0aGF0IFBldHJhIGFuZCBKYW4gYXNzaWduIHRvIHRoZSBpLXRoIGdvb2RpZSwgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VyczogdGhlIHZhbHVlIFBldHJhIGdldHMgYW5kIHRoZSB2YWx1ZSBKYW4gZ2V0cy4gQm90aCB2YWx1ZXMgbXVzdCBiZSBhY2NvcmRpbmcgdG8gdGhlaXIgb3duIHZhbHVhdGlvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: ytw0728