페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10382

인접과 연속 40s 1024MB

문제

두 플레이어 A와 B가 게임을 하고 있다. 이 게임에는 1번부터 N번까지 번호가 매겨진 N개의 타일과, 가로로 N칸이 일렬로 놓인(처음에는 모두 비어 있는) 보드가 있다.

플레이어들은 번갈아 가며 턴을 진행하고, 플레이어 A가 먼저 시작한다. 한 턴에 플레이어는 아직 사용하지 않은 타일 하나와 비어 있는 칸 하나를 골라 그 칸에 타일을 놓는다. 게임이 끝났을 때, (누가 놓았는지와 무관하게) 번호가 연속인 두 타일이 서로 인접한 칸에 놓여 있으면 플레이어 A가 승리한다. 그렇지 않으면 플레이어 B가 승리한다. 예를 들어 최종 보드가 1 2 3 4이거나 4 1 3 2이면 플레이어 A의 승리이고, 최종 보드가 3 1 4 2이면 플레이어 B의 승리이다. (연속된 두 수가 등장하는 순서는 어느 쪽이어도 상관없다.)

당신은 방금 두 플레이어가 게임을 하는 것을 지켜봤지만, 그들의 전략을 이해할 수 없었다. 어쩌면 두 사람은 합리적으로 플레이하지 않았을지도 모른다! 당신은 그들의 수를 최적 전략과 비교해 보기로 했다.

승리 상태(winning state)란, 현재 차례인 플레이어가 최적으로 플레이할 경우 상대가 무엇을 하든 승리를 보장할 수 있는 게임 상태를 뜻한다. 실수(mistake)란, 승리 상태에서 어떤 수를 두어 다음 턴에 상대에게 승리 상태를 넘겨주는 수를 뜻한다. (마지막 턴에는 실수가 불가능함에 유의하라. 마지막 턴이 승리 상태에서 시작했다면, 그 플레이어가 둘 수 있는 유일한 수가 곧바로 승리로 이어질 수밖에 없기 때문이다.)

주어진 N번의 수를 바탕으로, 각 플레이어가 저지른 실수의 개수를 세어라.


입력

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 정수 N이 주어진 한 줄로 시작하며, 이는 게임에 있는 타일의 개수이다(즉, 턴의 수이자 보드의 칸 수이기도 하다).

그 다음 N줄이 이어진다. 이 중 i번째 줄(1부터 센다)에는 두 정수 Mi와 Ci가 주어진다. 이는 각각 i번째 턴에 선택된 타일의 번호와, 그 타일이 놓인 칸의 인덱스(왼쪽 끝이 1, 오른쪽 끝이 N)를 의미한다.

i가 홀수일 때는 플레이어 A의 차례이고, i가 짝수일 때는 플레이어 B의 차례임에 유의하라.


출력

각 테스트 케이스마다 Case #x: a b 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, a는 플레이어 A가 저지른 실수의 총 개수, b는 플레이어 B가 저지른 실수의 총 개수이다.


예제 

3
6
2 2
3 5
4 3
6 6
1 4
5 1
4
4 1
1 3
3 4
2 2
4
3 1
2 2
4 3
1 4
Case #1: 2 1
Case #2: 0 0
Case #3: 0 0
어떤 게임이든 항상 플레이어 A의 승리 상태에서 시작한다는 점에 유의하라. 예를 들어 플레이어 A는 2번 타일을 2번 칸(왼쪽에서 두 번째 칸)에 둘 수 있다. 플레이어 B가 어떤 수를 두더라도, 타일 1과 3 중 적어도 하나는 사용되지 않은 상태이고, 칸 1과 3 중 적어도 하나는 비어 있다. 그러면 플레이어 A가 그 타일 중 하나를 그 칸 중 하나에 놓을 수 있고, 이후 게임이 어떻게 되든 플레이어 A의 승리가 보장된다. 샘플 케이스 #1에서 게임은 다음과 같이 진행된다: _ _ _ _ _ _. 위에서 설명했듯이 이는 플레이어 A의 승리 상태다. 턴 1: 플레이어 A가 2번 타일을 2번 칸에 둔다. _ 2 _ _ _ _. 위에서 설명했듯이 이는 플레이어 B의 승리 상태가 아니다. 플레이어 B는 남은 선택에 상관없이 승리를 보장할 수 없다. 턴 2: 플레이어 B가 3번 타일을 5번 칸에 둔다. _ 2 _ _ 3 _. 이는 플레이어 A의 승리 상태이다. 예를 들어 플레이어 A는 1번 타일을 3번 칸에 둘 수 있다. 턴 3: 플레이어 A가 4번 타일을 3번 칸에 둔다. _ 2 4 _ 3 _. 이는 플레이어 B의 승리 상태이다. 예를 들어 플레이어 B가 5번 타일을 1번 칸에 두면, 이후 플레이어 A가 무엇을 하든 플레이어 B의 승리가 보장된다. 따라서 플레이어 A의 마지막 수는 실수였다! 턴 4: 플레이어 B가 6번 타일을 6번 칸에 둔다. _ 2 4 _ 3 6. 이는 플레이어 A의 승리 상태이다. 플레이어 A가 1번 타일을 1번 칸에 둘 수 있기 때문이다. 따라서 플레이어 B의 마지막 수는 실수였다! 턴 5: 플레이어 A가 1번 타일을 4번 칸에 둔다. _ 2 4 1 3 6. 이는 플레이어 B의 승리 상태이므로 플레이어 A의 마지막 수는 실수였다! 턴 6: 플레이어 B가 5번 타일을 1번 칸에 둔다. 5 2 4 1 3 6. 게임이 끝났고 플레이어 B가 승리했다. 결과적으로 플레이어 A는 실수를 2번 했고 플레이어 B는 1번 했다. 샘플 케이스 #2에서는 몇몇 수가 위험해 보일 수 있지만, 이 문제의 정의에 따른 실수는 아무도 하지 않았다. 플레이어 A는 승리 상태를 플레이어 B에게 넘긴 적이 없고, 플레이어 B는 한 번도 승리 상태였던 적이 없으므로 실수할 기회가 없었다. 샘플 케이스 #3에서는 두 번째 수 이후에 게임의 결과가 결정되더라도(그 수가 인접하고 연속인 타일 쌍을 만들기 때문에), 각 게임에서 모든 타일을 반드시 놓아야 한다는 점을 유의하라. 또한 두 번째 수가 플레이어 A의 승리를 보장하더라도, 그 시점에 플레이어 B가 승리 상태였던 것은 아니므로 플레이어 B의 실수는 아니다.

출처

GCJ 2020wf B

로그인해야 코드를 작성할 수 있어요.