yes
Time Limit: 6 seconds
Memory Limit: 1024 MB
Rating: 1600
Problem StatementCharlie has an $N \cdot N$ matrix of integers. He plays a game involving this matrix with Gareth. Each player takes turns, with both players’ scores being $0$ at the start. Charlie goes first. When it’s his turn, Charlie removes a row of integers from the matrix and adds the sum of all the integers in that row to his score. When it becomes his turn, Gareth removes a column of integers from the matrix and adds the sum of all the integers in that column to his score. After all elements in the matrix has been removed, who has the higher score in the end? Output ‘C’ if Charlie has a higher score, ‘G’ if Gareth does and ‘D’ if it’s a draw. (without quotes). Assume both players play optimally. $1 \le N \le 1{,}000$
InputThe first line has integer $N$, followed by $N$ lines containing information about the starting matrix.
OutputOutput the answer.
Sample CasesSample Input 1: 1 0 2 -3 Sample Output 1: G Sample Input 2: 5 1 2 3 4 5 6 7 8 9 10 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 0 0 0 0 0 Sample Output 2: F Sample Input 3: 1 0 Sample Output 3: DExplanation
For the first test case, let's assume Frank removes the first row. Then Gareth's optimal move has to be the first column, as it has a $2$, rather than $-3$. Now Frank is forced to take $-3$ on his turn, resulting in Gareth's victory, as $-2 < 2$. Let's see what happens when Frank removes the second row. Frank adds $-1$ to his score, and Gareth adds $1$ to his score. Frank adds $0$ to his score. Gareth still wins, as $-1 < 1$. Therefore, Gareth wins with this starting configuration.
SourcesIanOJ Contest #3 (Div. 2) > Problem C
Submit | Back