문제
관영이는 시논과 게임을 한판 하려고 한다.
게임판은 N*M의 이차원 격자로 되어 있다.
그 게임판에는 여러 가지의 숫자가 있다.
플레이어는 턴마다 격자 안의 숫자를 선택할 수 있다.
다른 플레이어가 선택한 숫자는 선택할 수 없다.
관영이가 먼저 시작하며, 시논과 턴을 번갈아 가며 진행된다.
그리고 각자 점수는 선택한 숫자의 합이 되며, 점수가 높은 쪽이 승리한다.
점수가 같다면 후공인 시논이 승리한다.
한편, 이대로 게임을 진행하면 관영이가 너무 유리하기 때문에
시논은 경기 중 딱 한번 첫 턴을 제외하고 관영이의 턴을 스킵할 수 있다.
둘 다 최선을 다해 게임을 진행한다고 했을 때, 누가 이길지를 구해보자.
[입력예 설명]
첫번째 경우에는 관영이가 3을 가져갔을 때, 시논이 찬스를 사용하여 2와 1을 가져가면 관영이는 -1을 가져가 지게 된다.
두번째 경우에는 관영이가 5를 가져가는 순간, 시논은 다른 모든 숫자를 먹어도 이길 수 없다.
세번째 경우에는 관영이가 1을 가져갔을 때, 시논의 최적 전략은 찬스를 쓰지 않아 -1을 관영이가 먹게 하는 것이다.
입력
게임의 횟수 T가 주어진다.(1 <= T <= 20)
게임판의 크기 N, M이 주어진다.(1 <= N, M <= 100)
N줄에 걸쳐 M개의 숫자 a_ij가 주어진다. (1 <= i <= N, 1 <= j <= M, -105 <= a_ij <= 105)
출력
관영이가 이긴다면 K, 시논이 이긴다면 S를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 30점 | N, M <= 30 |
| #2 | 70점 | 제약조건 없음 |
예제
3
2 2
-1 1
2 3
2 2
0 1
2 5
3 3
0 0 0
0 -1 0
1 0 0
S
K
S
출처
william202
로그인해야 코드를 작성할 수 있어요.