죄수들의 도전

감옥에 $500$명의 죄수가 갇혀 있다. 어느 날 간수는 감옥에서 나갈 수 있는 기회를 주었다. 간수가 방 안에 동전이 든 두 개의 가방 A와 B를 놓았다. 각 가방에는 $1$개 이상 $N$개 이하의 동전이 들어 있다. 두 가방에 든 동전의 개수는 다르다. 간수는 죄수들에게 도전 기회를 준다. 죄수들의 목표는 동전이 적게 든 가방을 찾는 것이다.

방에는 동전이 든 가방 외에도 칠판이 있다. 칠판에는 항상 정수 하나만 쓸 수 있다. 처음에는 칠판에 $0$이 쓰여 있다.

간수는 죄수들에게 한 명씩 차례로 방에 들어오게 한다. 모든 죄수는 다른 죄수 중 누가 자기보다 먼저 이 방에 들어왔는지 알지 못하고, 또 자기 앞에 몇 명의 죄수가 방에 들어왔는지도 알지 못한다. 매번 죄수가 방에 들어올 때마다 칠판에 쓰여진 정수를 읽는다. 이 정수를 읽은 다음 가방 A와 B 중 하나를 골라야 한다. 다음 이 가방을 조사해서 이 가방에 몇 개의 동전이 있는지 알게 된다. 그 다음 죄수는 다음 두 행동 중 하나를 해야 한다.

• 칠판에 쓰여진 정수를 지우고 음이 아닌 정수를 쓴 다음 방을 나간다. 칠판에 먼저 쓰여진 정수와 같은 정수를 쓸 수도 있고 다른 정수를 쓸 수도 있다. 도전은 계속 이어진다 ($500$명의 죄수 모두가 방에 들어왔다가 나간 경우를 제외하고).
• 동전이 적게 든 가방을 고르고 도전을 종료한다.

한 번 방을 나간 죄수는 간수가 다시 방에 들여보내지 않는다.

만약 죄수 중 한 명이 동전이 적게 든 가방을 정확히 맞추면 죄수들이 도전에서 이긴다. 만약 죄수 중 한 명이라도 동전이 적게 든 가방을 틀리거나, $500$명의 죄수 모두가 방에 들어갔다 나왔지만 동전이 적게 든 가방을 맞추려고 아무도 시도하지 않았다면 죄수들이 진다.

도전을 시작하기 전에 죄수들은 강당에 모여서 $3$단계로 이루어지는 다음 공통 전략을 정했다.

• 칠판에 쓸 수 있는 음이 아닌 정수의 최대값 $x$를 정한다.
• 방에 들어갔을 때 칠판에 정수 $i$가 쓰여져 있다면 ($0 \le i \le x$) 어느 가방을 조사할 것인지를 정한다.
• 조사한 가방의 동전 개수를 알게 되면 어떤 행동을 할 것인지를 결정한다. 보다 구체적으로 칠판에 정수 $i$가 쓰여져 있고 ($0 \le i \le x$) 조사한 가방에 동전 $j$개가 들어 있다면 ($1 \le j \le N$) 다음 두 행동 중 하나를 하는 것으로 결정해야 한다.
  • $0$ 이상 $x$ 이하인 어떤 정수를 칠판에 쓸지, 또는
  • 어느 가방을 동전이 적은 쪽으로 고를지.

죄수들이 도전에서 이기면 간수는 죄수들을 $x$일간 더 가둔 다음에 모두 풀어줄 것이다.

당신이 할 일은 죄수들이 이 도전을 이길 수 있는 전략을 고안하는 것이다 (가방 A, B에 있는 동전 개수와 무관하게). 여러분이 제출한 해법의 점수는 $x$의 값에 따라 달라진다 (자세한 내용은 Subtasks 참조).

구현 세부사항

다음 함수를 구현해야 한다.

int[][] devise_strategy(int N)

• $N$: 가방 하나에 들어갈 수 있는 동전의 최대 개수.
• 이 함수는 $N + 1$개의 정수를 저장하는 배열의 배열 $s$를 리턴해야 하며, 이 배열이 당신의 전략을 설명한다. $x$의 값은 배열 $s$의 길이에서 $1$을 뺀 값이다. $0 \le i \le x$인 각 $i$에 대해서 배열 $s[i]$는 죄수가 방에 들어갔을 때 칠판에서 정수 $i$를 읽었다면 무엇을 해야 하는지를 나타낸다.
  1. 죄수가 만약 가방 A를 조사해봐야 하면 $s[i][0]$의 값은 $0$이고, 만약 가방 B를 조사해봐야 하면 $1$이다.
  2. $j$가 조사해본 가방에 들어 있는 동전 개수라고 하자. 그렇다면 죄수는 다음 행동을 해야 한다.
     • 만약 $s[i][j]$의 값이 $-1$이라면 죄수는 가방 A를 동전이 적게 든 가방으로 고른다.
     • 만약 $s[i][j]$의 값이 $-2$라면 죄수는 가방 B를 동전이 적게 든 가방으로 고른다.
     • 만약 $s[i][j]$의 값이 음이 아니라면 죄수는 이 정수를 칠판에 써야 한다. $s[i][j]$의 값은 최대 $x$라는 데 주의하라.
• 이 함수는 정확히 한 번 호출된다.

예제

다음 호출을 생각해보자.

devise_strategy(3)

$v$가 죄수가 방에 들어왔을 때 칠판에 쓰여진 정수라고 하자. 정답을 내는 전략 중 하나는 다음과 같다.

• 만약 $v = 0$이라면 (처음 시작할 때를 포함해서) 가방 A를 조사한다.
  • 동전 $1$개가 들어 있다면 가방 A를 동전이 적게 든 가방으로 고른다.
  • 동전 $3$개가 들어 있다면 가방 B를 동전이 적게 든 가방으로 고른다.
  • 동전 $2$개가 들어 있다면 칠판에 $1$을 쓴다 ($0$을 덮어쓴다).
• 만약 $v = 1$이라면 가방 B를 조사한다.
  • 동전 $1$개가 들어 있다면 가방 B를 동전이 적게 든 가방으로 고른다.
  • 동전 $3$개가 들어 있다면 가방 A를 동전이 적게 든 가방으로 고른다.
  • 동전 $2$개가 들어 있다면 칠판에 $0$을 쓴다 ($1$을 덮어쓴다). 이 경우는 절대 일어나지 않는다는 데 주목하자. 왜냐하면 이때 두 가방 모두 동전 $2$개가 있는데, 두 가방에 같은 수의 동전이 들어 있는 것을 허용하지 않기 때문이다.

이 전략을 표현하려면 함수는 [[0, -1, 1, -2], [1, -2, 0, -1]]를 리턴해야 한다. 리턴된 배열의 길이는 $2$이고 $x$의 값은 $2 - 1 = 1$이다.

제약 조건

• $2 \le N \le 5000$

서브태스크

1. (5점) $N \le 500$, $x$는 $500$ 이하여야 한다.
2. (5점) $N \le 500$, $x$는 $70$ 이하여야 한다.
3. (90점) $x$는 $60$ 이하여야 한다.

만약 테스트 케이스 중 어느 경우에서든 devise_strategy가 리턴한 배열이 정확한 전략을 나타내지 않는 경우, 이 서브태스크에 대해서 당신은 $0$점을 얻는다.

서브태스크 3은 부분 점수가 있다. 이 서브태스크에 대해서 리턴한 모든 배열에서 $x$ 값의 최대가 $m$이라고 하자. 이 서브태스크에서 당신의 점수는 다음 표와 같다.

• line $1$: $N$
• line $2 + k$ ($0 \le k$): $A[k] \; B[k]$
• last line: $-1$

첫 줄과 마지막 줄을 제외한 각각의 줄들은 시나리오를 설명한다. 시나리오 $k$는 $2 + k$번째 줄에 설명되어 있다. 시나리오 $k$에서는 가방 A에 $A[k]$개의 동전이 있고 가방 B에 $B[k]$개의 동전이 있다.

샘플 그레이더는 먼저 devise_strategy(N)를 호출한다. $x$의 값은 이 호출에서 리턴한 배열의 길이에서 $1$을 뺀 값이다. 이때 샘플 그레이더가 devise_strategy가 리턴한 배열이 Implementation Details에서 설명한 제약 조건을 따르지 않는다면 다음 에러 메시지 중 하나를 출력하고 종료한다.

• s is an empty array: $s$가 길이가 $0$인 배열이다 (타당한 전략을 표현하지 않는다).
• s[i] contains incorrect length: $s[i]$의 길이가 $N + 1$이 아닌 인덱스 $i$ ($0 \le i \le x$)가 있다.
• First element of s[i] is non-binary: $s[i][0]$의 값이 $0$ 또는 $1$이 아닌 인덱스 $i$ ($0 \le i \le x$)가 있다.
• s[i][j] contains incorrect value: $s[i][j]$의 값이 $-2$ 이상 $x$ 이하가 아닌 인덱스 $i, j$ ($0 \le i \le x$, $1 \le j \le N$)가 있다.

그렇지 않다면 샘플 그레이더는 두 가지 출력을 한다.

먼저 샘플 그레이더는 다음 양식으로 여러분의 전략의 결과를 출력한다.

• line $1 + k$ ($0 \le k$): 시나리오 $k$에 대한 여러분의 전략의 결과.

만약 이 전략을 써서 죄수가 가방 A를 동전이 적은 쪽으로 골랐다면 출력은 글자 A이다. 만약 이 전략을 써서 죄수가 가방 B를 동전이 적은 쪽으로 골랐다면 출력은 글자 B이다. 만약 이 전략을 썼는데 어느 죄수도 동전이 적은 쪽 가방을 고르지 못했다면 출력은 글자 X이다.

또한 샘플 그레이더는 현재 디렉토리에 log.txt 파일을 다음 양식으로 출력한다.

• line $1 + k$ ($0 \le k$): $w[k][0] \; w[k][1] \; \ldots$

$1 + k$번째 줄에 출력된 수열은 시나리오 $k$에서 칠판에 쓰여지는 정수들이다. 보다 구체적으로 $w[k][l]$는 방에 $(l + 1)$번째 들어간 죄수가 칠판에 쓰는 정수이다.

샘플 그레이더는 다음 양식으로 입력을 읽는다.