1색 칠하기

$N$마리의 정령들이 원형으로 둘러앉아 색칠놀이를 한다. 각 정령에게는 $1, 2, \ldots, N$번 번호가 붙어 있고, $i$번 정령의 색은 $i$이다. 각 정령은 시계방향을 기준으로 다음 위치에 있는 정령을 바라보고 있으며, 항상 자신이 바라보는 정령을 색칠한다. $A$번 색을 가진 정령이 다른 정령을 색칠하면, 그 정령의 색은 $A$번 정령의 색과 같아진다. 위 그림에서 1번 정령이 4번 정령을 색칠하면 4번 정령의 색이 노란색(1번 색)이 된다.

유현이는 정령들과 함께 있고, 재율이는 다른 곳에 있다. 재율이는 메신저로 유현이와 소통하며 모든 정령을 1번 색으로 칠하려고 한다.

재율이는 유현이를 통해 정령들에게 자신의 앞에 있는 정령을 색칠하라고 지시할 수 있다. 그러면 각 정령은 앞에 있는 정령을 자신의 색으로 칠한다. 다만 유현이는 한 번에 최대 한 마리의 정령에게만 지시를 내릴 수 있다.

앞선 상황에서 3번 정령에게 지시를 내리면 왼쪽 그림과 같은 상황이 된다. 그 후 4번, 5번 정령에게 지시를 내리면 오른쪽 그림과 같은 상황이 된다.

재율이는 유현이에게 특정 색의 정령이 있는지 물어볼 수 있다. 그러면 유현이는 정령들이 모인 모습을 대강 보고 '있다' 또는 '없다' 중 하나로 대답한다. 유현이는 여러 색을 한꺼번에 셀 만큼 머리가 좋지 않아서, 오직 한 종류의 색에 대해서만 개수를 셀 수 있다. 정령을 세는 데 시간이 꽤 걸리므로 그 사이에 정령들은 본연의 색으로 돌아온다. 위 상황에서 재율이가 노란 정령이 있는지 물어보면, 유현이는 '노란 정령이 있다'고 대답한다. 정령을 센 후 1, 2, 3, 4, 5번 정령은 각각 노랑, 보라, 초록, 파랑, 빨강으로 변한다. 유현이가 색을 세기 전까지는 정령의 색이 변하지 않으므로, 유현이의 대답이 틀릴 가능성은 없다.

유현이가 정령들의 배치 상황을 사진으로 찍어 재율이에게 보내면 좋겠지만, 모바일 데이터가 얼마 남지 않아 그럴 수 없다. 즉, 재율이는 정령들의 배치를 모른 채 모든 정령을 1번 색으로 바꿔야 한다.

재율이를 도와 모든 정령을 1번 색으로 바꾸는 프로그램을 작성해 보자.

당신은 정령들을 모두 1번 색으로 칠하는 함수 void ColoringSame(int N)을 작성해야 한다. (ColoringSame(N) 함수는 coloring.c 또는 coloring.cpp에 있다.)

인수 N은 정령의 수이다 ($3 \le N \le 100$).

ColoringSame 함수 안에서 Color(A)와 GetColor(C)를 여러 번 호출할 수 있다.

void Color(int A)는 A번 정령에게 자기 앞에 있는 정령을 색칠하라고 지시하는 함수이다. A: 지시할 정령의 번호 ($1 \le A \le N$)

int GetColor(int C)는 색깔이 C인 정령이 있는지 묻는 함수이다. 이 함수를 호출하면 모든 정령의 색이 초기화된다. C: 물어볼 색깔의 번호 ($1 \le C \le N$) 반환값: 색깔이 C인 정령이 없으면 0, 있으면 1

ColoringSame(N) 함수가 끝났을 때 모든 정령의 색이 1이어야 한다. 그렇지 않으면 채점 프로그램은 Wrong[1]을 출력한다. 인자가 범위를 벗어나면 Wrong[2]를 출력하고 프로그램이 즉시 끝난다. Color와 GetColor를 허용된 횟수를 넘겨 호출하면 Wrong[3]을 출력하고 프로그램이 즉시 끝난다.

Color는 최대 7300번, GetColor는 최대 200번 호출할 수 있다.

채점 프로그램은 처음에 정령의 배치를 정하면, 당신의 호출에 따라 배치를 바꾸지 않는다(Non-Adaptive). 메모리 접근, 시스템 호출 등 비정상적인 방법을 쓰면 오답 처리될 수 있으니 유의하라.

문제 페이지에서 샘플 코드를 내려받을 수 있다. Visual Studio, Eclipse, Code::Blocks 같은 IDE를 쓴다면 coloring.cpp, coloring.h, grader.cpp(또는 coloring.c, coloring.h, grader.c)를 한 프로젝트에 넣고 컴파일하면 된다. 터미널에서 컴파일할 때는 아래 명령어를 쓴다. C / gcc: gcc -Wall -lm -static -o coloring -O2 coloring.c grader.c C++ / G++: g++ -Wall -lm -static -o coloring -O2 coloring.cpp grader.cpp 제출은 coloring.c 또는 coloring.cpp 코드만 하면 된다.