전구 게임

친한 친구 민형이와 선율이가 $N$개의 버튼과 $N-1$개의 전구가 있는 게임판에서 게임을 한다. $N$은 항상 짝수이다.

민형이와 선율이가 번갈아 버튼을 누른다. 매 순간 두 사람은 아직 눌리지 않은 버튼 중 하나를 골라 누른다. 선율이가 버튼을 누르면, 민형이가 직전에 누른 버튼과 선율이가 누른 버튼 사이에 있는 모든 전구의 상태가 바뀐다. 꺼진 전구는 켜지고, 켜진 전구는 꺼진다.

처음에는 모든 전구가 꺼져 있다. 이 상태에서 민형이가 2번 버튼을 누르고 선율이가 4번 버튼을 누르면, 게임판은 아래와 같이 바뀐다.

여기서 민형이가 3번 버튼을 누르고 선율이가 5번 버튼을 누르면, 게임판은 아래와 같이 바뀐다.

$N$개의 버튼을 모두 누르면 게임이 끝난다. 켜진 전구가 꺼진 전구보다 많으면 선율이가 이기고, 그렇지 않으면 민형이가 이긴다.

선율이는 긴장감을 주려고, 진 사람이 민형이와 선율이를 포함한 16명의 친구에게 치킨을 쏘자고 제안했다. 16명분 치킨은 값이 비싸서, 선율이가 지면 큰 돈을 내야 할 수도 있다. 선율이가 이길 수 있도록 전략을 짜는 프로그램을 작성하여라. 선율이가 이길 수 있는 전략은 항상 존재한다.

게임을 진행하는 함수 Init(N)과 MakeTurn(M)을 작성해야 한다. (Init(N)과 MakeTurn(M) 함수는 bulb.c / bulb.cpp에 있다.)

void Init(int N) 함수는 처음에 한 번 호출되며, 여기서 전처리를 할 수 있다.

• $N$: 전구의 수 ($2 \le N \le 1\,000$, $N$은 짝수)

int MakeTurn(int M) 함수는 Init 함수가 호출된 뒤 $N/2$번 호출된다. 이때 선율이가 자신의 턴에 눌러야 하는 버튼의 번호를 반환해야 한다.

• $M$: 민형이가 자신의 턴에 누른 버튼의 번호 ($1 \le M \le N$)
• 반환값: 선율이가 자신의 턴에 누르는 버튼의 번호 ($1 \le$ 반환값 $\le N$)

게임이 정상적으로 끝나고 선율이가 졌다면 Wrong[1]을 출력한다. MakeTurn(M)의 반환값이 범위를 벗어나거나 이미 눌렀던 버튼의 번호라면 Wrong[2]를 출력하고 프로그램이 즉시 끝난다.

예시 프로그램은 다음과 같다.

#include "bulb.h"

void Init(int N) {
	// do nothing
}

int MakeTurn(int M) {
	return (M+2)%7;
}

메모리 접근, 시스템 호출 등 비정상적인 방법을 쓰면 오답 처리될 수 있다.

샘플 코드는 문제 페이지에서 내려받을 수 있다. Visual Studio, Eclipse, Code::Blocks 같은 IDE를 쓴다면 bulb.cpp, bulb.h, grader.cpp (또는 bulb.c, bulb.h, grader.c)를 한 프로젝트에 넣고 컴파일하면 된다.

터미널에서 컴파일한다면 아래 명령어를 쓰면 된다.

• C / gcc: gcc -Wall -lm -static -o bulb -O2 bulb.c grader.c
• C++ / G++: g++ -Wall -lm -static -o bulb -O2 bulb.cpp grader.cpp

프로그램을 실행하면 표준입력으로 $N$을 받고, 이어서 민형이가 누른 버튼의 번호를 받는다. 채점기는 선율이가 누른 버튼의 번호(MakeTurn 함수의 반환값)를 출력한다. 게임이 끝나면 샘플 채점기가 정답 여부를 출력한다.

답안으로는 bulb.c 또는 bulb.cpp 코드만 제출하면 된다.