3662번 - 보석 분배 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 78 | 30 | 23 | 53.488% |
문제
민혁이와 민규는 보석으로 가득찬 박스를 가지고 있고, 이제 이 보석을 나누려고 한다. 하지만, 각 보석의 가치가 다르기 때문에 공정하게 보석을 나누는 것은 매우 어려운 일이다.
보석을 나누기 위해서, 턴을 번갈아가면서 보석을 하나씩 가져간다. 보석이 남아있지 않을 때 까지 턴을 번갈아가며, 누가 먼저 시작할지는 동전을 던져서 결정한다.
민혁이와 민규는 서로 다른 전략을 가지고 보석을 고르려고 한다. 민혁이는 남아있는 보석 중에서 민혁이에게 가장 가치있는 보석을 고른다. 만약, 그러한 보석이 여러 가지라면, 민규에게 가장 가치가 없는 보석을 고른다.
민규는 최종 가치의 합이 최대가 되게 보석을 고른다. 만약, 그러한 보석이 여러 가지라면, 민혁이의 최종 가치가 최대한 크게 되는 보석을 고른다.
누가 턴을 먼저 시작할지와, 각 사람이 느끼는 보석의 가치가 주어졌을 때, 두 사람이 가져가는 보석의 가치를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 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
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 B번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호