Coreputer

새로운 컴퓨팅 기계인 Coreputer에는 $0$부터 $N-1$까지 번호가 매겨진 $N$개의 코어가 있다. 최근 유지보수 과정에서 코어 중 일부가 오작동하고 있다는 사실이 밝혀졌다. 구체적으로 어느 코어가 오작동하는지는 알 수 없지만, 오작동하는 코어가 적어도 하나는 있다.

오작동하는 코어를 찾기 위해 Coreputer는 진단 스캔을 실행할 수 있다. 각 스캔에서 사용자는 어떤 $0\le l\le N$에 대해 서로 다른 코어들로 이루어진 (비어 있을 수도 있는) 그룹 $T[0],\ldots,T[l-1]$에 태그를 지정한다. 나머지 코어에는 태그가 지정되지 않는다. 그런 다음 Coreputer는 태그가 지정된 코어들과 태그가 지정되지 않은 코어들의 성능을 측정한다. 마지막으로, 두 그룹 중 어느 쪽에 오작동하는 코어가 더 많이 들어 있는지, 또는 두 그룹에 오작동하는 코어가 같은 수만큼 들어 있는지를 보고한다. 빈 그룹에는 오작동하는 코어가 $0$개 있다는 점에 유의하라.

여러 번의 진단 스캔을 실행하여 오작동하는 코어를 찾는 것이 여러분의 과제이다.

구현 세부사항

다음 프로시저를 구현해야 한다.

int[] malfunctioning_cores(int N)

• $N$: 코어의 수.
• 이 프로시저는 배열 $c=[c[0],c[1],\ldots,c[N-1]]$을 반환해야 한다. 여기서 $0$ 이상 $N-1$ 이하인 각 $i$에 대해, 코어 $i$가 오작동하면 $c[i]=1$이고, 그렇지 않으면 $c[i]=0$이다.
• 이 프로시저는 각 테스트 케이스마다 정확히 한 번 호출된다.

위 프로시저는 다음 프로시저를 호출할 수 있다.

int run_diagnostic(int[] T)

• $T$: 서로 다른 코어들로 이루어진 배열.
• 이 프로시저는 다음 값을 반환한다.
  • 태그가 지정된 오작동 코어의 수가 태그가 지정되지 않은 오작동 코어의 수보다 많으면 $1$;
  • 태그가 지정된 오작동 코어의 수와 태그가 지정되지 않은 오작동 코어의 수가 같으면 $0$;
  • 태그가 지정된 오작동 코어의 수가 태그가 지정되지 않은 오작동 코어의 수보다 적으면 $-1$.
• 이 프로시저는 각 테스트 케이스에서 최대 $32$번 호출할 수 있다.

그레이더는 적응형이 아니다. 즉, 오작동하는 코어의 집합은 malfunctioning_cores가 호출되기 전에 고정된다.

예제

$N=4$개의 코어가 있고 코어 $2$만 오작동하는 상황을 생각해 보자.

프로시저 malfunctioning_cores는 다음과 같이 호출된다.

malfunctioning_cores(4)

이 프로시저는 다음과 같이 run_diagnostic을 호출할 수 있다.

첫 번째 호출에서는 태그가 지정된 오작동 코어는 없고 태그가 지정되지 않은 코어 중 하나가 오작동하므로, 프로시저는 $-1$을 반환한다.

세 번째 호출이 $1$을 반환한 뒤에는 태그가 지정된 코어 중 적어도 하나(즉, 코어 $2$)가 오작동한다는 것이 분명하다. 그런데 이 경우 태그가 지정되지 않은 오작동 코어의 수는 반드시 0이어야 하므로, 다른 어떤 코어도 오작동하지 않는다고 결론 내릴 수 있다.

따라서 프로시저 malfunctioning_cores는 $[0,0,1,0]$을 반환해야 한다.

제약 조건

• $2\le N\le 16$

서브태스크

1. (20점) $N=2$
2. (40점) 오작동하는 코어의 수가 짝수이다.
3. (40점) 추가 제약 조건이 없다.

어떤 테스트 케이스에서든 프로시저 run_diagnostic의 호출이 구현 세부사항에 설명된 제약 조건을 따르지 않거나 malfunctioning_cores의 반환값이 올바르지 않으면, 해당 서브태스크에서 여러분의 풀이가 받는 점수는 $0$점이다.

각 서브태스크에서 부분 점수를 받을 수 있다. 모든 테스트 케이스에서 프로시저 run_diagnostic을 호출한 횟수의 최댓값을 $q$라고 하자. 그러면 다음 표에 따라 해당 서브태스크 점수의 일정 비율을 받는다.

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

• 1번째 줄: $N$
• 2번째 줄: $M[0]\ M[1]\ \ldots\ M[N-1]$

여기서 $0$ 이상 $N-1$ 이하인 각 $i$에 대해, 코어 $i$가 오작동하면 $M[i]=1$이고, 그렇지 않으면 $M[i]=0$이다.

샘플 그레이더는 malfunctioning_cores를 호출하기 전에 오작동하는 코어가 적어도 하나 있는지 확인한다. 이 조건이 충족되지 않으면 No Malfunctioning Cores라는 메시지를 출력하고 종료한다.

샘플 그레이더가 프로토콜 위반을 감지하면 샘플 그레이더의 출력은 Protocol Violation: <MSG>이다. 여기서 <MSG>는 다음 오류 메시지 중 하나이다.

• invalid array: run_diagnostic 호출에서 배열 $T$가
  • $N$개보다 많은 원소를 가지거나,
  • $0$ 이상 $N-1$ 이하인 정수가 아닌 원소를 포함하거나,
  • 같은 원소를 적어도 두 번 포함한다.
• too many calls: run_diagnostic의 호출 횟수가 $32$를 초과한다.

그렇지 않으면, 어떤 음이 아닌 정수 $n$에 대해 malfunctioning_cores가 반환한 배열의 원소를 $c[0],c[1],\ldots,c[n-1]$이라고 하자.

샘플 그레이더의 출력은 다음 형식이다.

• 1번째 줄: $c[0]\ c[1]\ \ldots\ c[n-1]$
• 2번째 줄: run_diagnostic의 호출 횟수