시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cdWJiZmNcdWQ2MDFcdWM3NzRcdWM2NDAgXHViYmZjXHVhZGRjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODA0XHViN2I1XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWJjZjRcdWMxMWRcdWM3NDQgXHVhY2UwXHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViYmZjXHVkNjAxXHVjNzc0XHViMjk0IFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWJjZjRcdWMxMWQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YzVkMFx1YWM4YyBcdWFjMDBcdWM3YTUgXHVhYzAwXHVjZTU4XHVjNzg4XHViMjk0IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YmNmNFx1YzExZFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0LCBcdWJiZmNcdWFkZGNcdWM1ZDBcdWFjOGMgXHVhYzAwXHVjN2E1IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWM1YzZcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYmZjXHVhZGRjXHViMjk0IFx1Y2Q1Y1x1Yzg4NSBcdWFjMDBcdWNlNThcdWM3NTggXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWFjOGMgXHViY2Y0XHVjMTFkXHVjNzQ0IFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHViY2Y0XHVjMTFkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWM4ODUgXHVhYzAwXHVjZTU4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWQwNmNcdWFjOGMgXHViNDE4XHViMjk0IFx1YmNmNFx1YzExZFx1Yzc0NCBcdWFjZTBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjIwNFx1YWMwMCBcdWQxMzRcdWM3NDQgXHViYTNjXHVjODAwIFx1YzJkY1x1Yzc5MVx1ZDU2MFx1YzljMFx1YzY0MCwgXHVhYzAxIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWIyOTBcdWIwN2NcdWIyOTQgXHViY2Y0XHVjMTFkXHVjNzU4IFx1YWMwMFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWJjZjRcdWMxMWRcdWM3NTggXHVhYzAwXHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUIChUICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJjZjRcdWMxMWRcdWM3NTggXHVhYzFjXHVjMjE4IG4gKDEgJmxlOyBuICZsZTsgMTAwMCk8XC9saT5cclxuXHQ8bGk+XHViYTNjXHVjODAwIFx1ZDEzNFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1Yzc3NFx1Yjk4NCAoXHViYmZjXHVkNjAxXHVjNzc0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtQZXRyYSZxdW90OywgXHViYmZjXHVhZGRjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDtKYW4mcXVvdDspPFwvbGk+XHJcblx0PGxpPm5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMFx1YzExYyBcdWJiZmNcdWQ2MDFcdWM3NzRcdWFjMDAgXHViMjkwXHViMDdjXHViMjk0IFx1YWMwMFx1Y2U1OCBwPHN1Yj5pPFwvc3ViPiwgXHViYmZjXHVhZGRjXHVhYzAwIFx1YjI5MFx1YjA3Y1x1YjI5NCBcdWFjMDBcdWNlNTggajxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBwPHN1Yj5pPFwvc3ViPiwgajxzdWI+aTxcL3N1Yj4mbmJzcDsmbGU7IDEgMDAwKTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjI5NCBcdWJjZjRcdWMxMWQgXHVhYzAwXHVjZTU4XHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGcmVlIEdvb2RpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlBldHJhIGFuZCBKYW4gaGF2ZSBqdXN0IHJlY2VpdmVkIGEgYm94IGZ1bGwgb2YgZnJlZSBnb29kaWVzLCBhbmQgd2FudCB0byBkaXZpZGUgdGhlIGdvb2RpZXMgYmV0d2VlbiB0aGVtLiBIb3dldmVyLCBpdCBpcyBub3QgZWFzeSB0byBkbyB0aGlzIGZhaXJseSwgc2luY2UgdGhleSBib3RoIHZhbHVlIGRpZmZlcmVudCBnb29kaWVzIGRpZmZlcmVudGx5LjxcL3A+XHJcblxyXG48cD5UbyBkaXZpZGUgdGhlIGdvb2RpZXMsIHRoZXkgaGF2ZSBkZWNpZGVkIHVwb24gdGhlIGZvbGxvd2luZyBwcm9jZWR1cmU6IHRoZXkgY2hvb3NlIGdvb2RpZXMgb25lIGJ5IG9uZSwgaW4gdHVybiwgdW50aWwgYWxsIHRoZSBnb29kaWVzIGFyZSBjaG9zZW4uIEEgY29pbiBpcyB0b3NzZWQgdG8gZGVjaWRlIHdobyBnZXRzIHRvIGNob29zZSB0aGUgZmlyc3QgZ29vZGllLjxcL3A+XHJcblxyXG48cD5QZXRyYSBhbmQgSmFuIGhhdmUgZGlmZmVyZW50IHN0cmF0ZWdpZXMgaW4gZGVjaWRpbmcgd2hhdCB0byBjaG9vc2UuIFdoZW4gZmFjZWQgd2l0aCBhIGNob2ljZSwgUGV0cmEgYWx3YXlzIHNlbGVjdHMgdGhlIGdvb2RpZSB0aGF0IGlzIG1vc3QgdmFsdWFibGUgdG8gaGVyLiBJbiBjYXNlIG9mIGEgdGllLCBzaGUgaXMgdmVyeSBjb25zaWRlcmF0ZSBhbmQgcGlja3MgdGhlIG9uZSB0aGF0IGlzIGxlYXN0IHZhbHVhYmxlIHRvIEphbi4gKFNpbmNlIFBldHJhIGFuZCBKYW4gYXJlIGdvb2QgZnJpZW5kcywgdGhleSBrbm93IGV4YWN0bHkgaG93IG11Y2ggdmFsdWUgdGhlIG90aGVyIHBsYWNlcyBvbiBlYWNoIGdvb2RpZS4pPFwvcD5cclxuXHJcbjxwPkphbiZyc3F1bztzIHN0cmF0ZWd5LCBob3dldmVyLCBjb25zaXN0cyBvZiBtYXhpbWl6aW5nIGhpcyBvd24gZmluYWwgdmFsdWUuIEhlIGlzIGFsc28gdmVyeSBjb25zaWRlcmF0ZSwgc28gaWYgbXVsdGlwbGUgY2hvaWNlcyBsZWFkIHRvIHRoZSBzYW1lIG9wdGltYWwgcmVzdWx0LCBoZSBwcmVmZXJzIFBldHJhIHRvIGhhdmUgYXMgbXVjaCBmaW5hbCB2YWx1ZSBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgcmVzdWx0IG9mIHRoZSBpbml0aWFsIGNvaW4gdG9zcy4gQWZ0ZXIgSmFuIGFuZCBQZXRyYSBoYXZlIGZpbmlzaGVkIGRpdmlkaW5nIGFsbCB0aGUgZ29vZGllcyBiZXR3ZWVuIHRoZW1zZWx2ZXMsIHdoYXQgaXMgdGhlIHRvdGFsIHZhbHVlIG9mIHRoZSBnb29kaWVzIGVhY2ggb2YgdGhlbSBlbmRzIHVwIHdpdGg/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2YgZ29vZGllcy48XC9saT5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhIHN0cmluZywgZWl0aGVyICZsZHF1bztQZXRyYSZyZHF1bzsgb3IgJmxkcXVvO0phbiZyZHF1bzs6IHRoZSBwZXJzb24gdGhhdCBjaG9vc2VzIGZpcnN0LjxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIHdpdGggdHdvIGludGVnZXJzIHA8c3ViPmk8XC9zdWI+IGFuZCBqPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IHA8c3ViPmk8XC9zdWI+LCBqPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwKSBlYWNoOiB0aGUgdmFsdWVzIHRoYXQgUGV0cmEgYW5kIEphbiBhc3NpZ24gdG8gdGhlIGktdGggZ29vZGllLCByZXNwZWN0aXZlbHkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzOiB0aGUgdmFsdWUgUGV0cmEgZ2V0cyBhbmQgdGhlIHZhbHVlIEphbiBnZXRzLiBCb3RoIHZhbHVlcyBtdXN0IGJlIGFjY29yZGluZyB0byB0aGVpciBvd24gdmFsdWF0aW9ucy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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