시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZyZWUgR29vZGllcyIsImRlc2NyaXB0aW9uIjoiPHA+UGV0cmEgYW5kIEphbiBoYXZlIGp1c3QgcmVjZWl2ZWQgYSBib3ggZnVsbCBvZiBmcmVlIGdvb2RpZXMsIGFuZCB3YW50IHRvIGRpdmlkZSB0aGUgZ29vZGllcyBiZXR3ZWVuIHRoZW0uIEhvd2V2ZXIsIGl0IGlzIG5vdCBlYXN5IHRvIGRvIHRoaXMgZmFpcmx5LCBzaW5jZSB0aGV5IGJvdGggdmFsdWUgZGlmZmVyZW50IGdvb2RpZXMgZGlmZmVyZW50bHkuPFwvcD5cclxuXHJcbjxwPlRvIGRpdmlkZSB0aGUgZ29vZGllcywgdGhleSBoYXZlIGRlY2lkZWQgdXBvbiB0aGUgZm9sbG93aW5nIHByb2NlZHVyZTogdGhleSBjaG9vc2UgZ29vZGllcyBvbmUgYnkgb25lLCBpbiB0dXJuLCB1bnRpbCBhbGwgdGhlIGdvb2RpZXMgYXJlIGNob3Nlbi4gQSBjb2luIGlzIHRvc3NlZCB0byBkZWNpZGUgd2hvIGdldHMgdG8gY2hvb3NlIHRoZSBmaXJzdCBnb29kaWUuPFwvcD5cclxuXHJcbjxwPlBldHJhIGFuZCBKYW4gaGF2ZSBkaWZmZXJlbnQgc3RyYXRlZ2llcyBpbiBkZWNpZGluZyB3aGF0IHRvIGNob29zZS4gV2hlbiBmYWNlZCB3aXRoIGEgY2hvaWNlLCBQZXRyYSBhbHdheXMgc2VsZWN0cyB0aGUgZ29vZGllIHRoYXQgaXMgbW9zdCB2YWx1YWJsZSB0byBoZXIuIEluIGNhc2Ugb2YgYSB0aWUsIHNoZSBpcyB2ZXJ5IGNvbnNpZGVyYXRlIGFuZCBwaWNrcyB0aGUgb25lIHRoYXQgaXMgbGVhc3QgdmFsdWFibGUgdG8gSmFuLiAoU2luY2UgUGV0cmEgYW5kIEphbiBhcmUgZ29vZCBmcmllbmRzLCB0aGV5IGtub3cgZXhhY3RseSBob3cgbXVjaCB2YWx1ZSB0aGUgb3RoZXIgcGxhY2VzIG9uIGVhY2ggZ29vZGllLik8XC9wPlxyXG5cclxuPHA+SmFuJnJzcXVvO3Mgc3RyYXRlZ3ksIGhvd2V2ZXIsIGNvbnNpc3RzIG9mIG1heGltaXppbmcgaGlzIG93biBmaW5hbCB2YWx1ZS4gSGUgaXMgYWxzbyB2ZXJ5IGNvbnNpZGVyYXRlLCBzbyBpZiBtdWx0aXBsZSBjaG9pY2VzIGxlYWQgdG8gdGhlIHNhbWUgb3B0aW1hbCByZXN1bHQsIGhlIHByZWZlcnMgUGV0cmEgdG8gaGF2ZSBhcyBtdWNoIGZpbmFsIHZhbHVlIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSByZXN1bHQgb2YgdGhlIGluaXRpYWwgY29pbiB0b3NzLiBBZnRlciBKYW4gYW5kIFBldHJhIGhhdmUgZmluaXNoZWQgZGl2aWRpbmcgYWxsIHRoZSBnb29kaWVzIGJldHdlZW4gdGhlbXNlbHZlcywgd2hhdCBpcyB0aGUgdG90YWwgdmFsdWUgb2YgdGhlIGdvb2RpZXMgZWFjaCBvZiB0aGVtIGVuZHMgdXAgd2l0aD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEgMDAwKTogdGhlIG51bWJlciBvZiBnb29kaWVzLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGEgc3RyaW5nLCBlaXRoZXIgJmxkcXVvO1BldHJhJnJkcXVvOyBvciAmbGRxdW87SmFuJnJkcXVvOzogdGhlIHBlcnNvbiB0aGF0IGNob29zZXMgZmlyc3QuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCB0d28gaW50ZWdlcnMgcDxzdWI+aTxcL3N1Yj4gYW5kIGo8c3ViPmk8XC9zdWI+ICgwICZsZTsgcDxzdWI+aTxcL3N1Yj4sIGo8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDApIGVhY2g6IHRoZSB2YWx1ZXMgdGhhdCBQZXRyYSBhbmQgSmFuIGFzc2lnbiB0byB0aGUgaS10aCBnb29kaWUsIHJlc3BlY3RpdmVseS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnM6IHRoZSB2YWx1ZSBQZXRyYSBnZXRzIGFuZCB0aGUgdmFsdWUgSmFuIGdldHMuIEJvdGggdmFsdWVzIG11c3QgYmUgYWNjb3JkaW5nIHRvIHRoZWlyIG93biB2YWx1YXRpb25zLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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