수 게임
시간 제한2초메모리 제한128 MB
수열에서 오른쪽 끝을 포함하는 연속 구간을 번갈아 가져가며 자신의 합을 최소화하는 게임에서, n이 최대 3000인 세 가지 게임의 승자를 구하는 문제입니다.
문제
n개의 정수 a1, a2, ..., an이 순서대로 놓여 있다. A와 B가 A부터 번갈아 차례를 진행한다.
한 차례에는 현재 남아 있는 수들 중 가장 오른쪽 수를 반드시 포함하는 연속한 하나 이상의 수를 가져간다. 현재 남은 수가 a1부터 ai까지라면, 어떤 k를 골라 ak, ak+1, ..., ai를 모두 가져간다. 가져간 수들은 제거되고, 다음 차례는 a1부터 a{k-1}까지만 남은 상태에서 진행된다.
수가 모두 없어지면 게임이 끝난다. 각 사람이 가져간 수의 합을 비교하여 합이 더 작은 사람이 이긴다. 합이 같으면 비긴다.
두 사람 모두 자신에게 가장 유리한 선택을 한다. 주어진 세 게임의 승자를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. (1 <= n <= 3,000)
다음 세 줄에는 각각 하나의 게임을 나타내는 n개의 정수가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 10,000 이하이다.
출력
세 줄을 출력한다. i번째 줄에는 입력의 i번째 게임에 해당하는 승자를 출력한다.
A가 이기면 A, B가 이기면 B, 비기면 D를 출력한다.