LR 스프링보드

형찬이는 놀이공원의 '스프링 야드' 어트랙션을 관리하는 관리자이다. 이 어트랙션은 스프링 $N$개가 일렬로 늘어서 있다. 스프링을 하나 밟으면 사람이 높이 떠올랐다가 바로 옆 스프링으로 떨어진다. 이 과정이 반복되면 보는 사람은 짜릿함을, 즐기는 사람은 스릴을 느낄 수 있다. 사람이 가장 왼쪽 스프링에서 왼쪽으로 떠오르거나 가장 오른쪽 스프링에서 오른쪽으로 떠오르면 매트에 떨어지며 한 번의 차례가 끝난다.

모든 스프링은 왼쪽 또는 오른쪽으로 살짝 기울어져 있다. 스프링을 밟으면 그 스프링이 보고 있는 방향으로 높이 떠오른다. 사람이 스프링을 밟아 떠오르면 그 스프링은 스스로 방향을 바꾼다. 왼쪽을 보던 스프링은 오른쪽으로, 오른쪽을 보던 스프링은 왼쪽으로 바뀐다.

벌써 날이 어두워져서 형찬이는 어트랙션을 정리하려고 한다. 놀이공원의 방침에 따라 모든 스프링은 왼쪽을 향해야 한다. 안전사고의 위험이 있으므로 형찬이는 손으로 스프링의 방향을 바꾸지 않고, 파란색 공을 이용해 방향을 바꾸려고 한다.

형찬이가 높은 곳에서 공을 떨어뜨리면 공은 이리저리 튀다가 왼쪽 끝 매트나 오른쪽 끝 매트에 떨어진다. 아래 그림처럼 형찬이가 3번째 스프링에 공을 떨어뜨린 뒤 첫 번째 스프링에 공을 떨어뜨리면 모든 스프링이 왼쪽을 보게 된다.

하지만 높은 곳에서는 $N$개 스프링이 어떤 방향을 향하는지 제대로 보이지 않는다. 형찬이는 처음부터 끝까지 스프링의 상태를 알 수 없다. 다만 떨어뜨린 공이 왼쪽 끝에서 멈추는지 오른쪽 끝에서 멈추는지는 쉽게 분간할 수 있다. 형찬이를 도와 공을 적절히 떨어뜨려 모든 스프링이 왼쪽을 보게 만드는 프로그램을 작성하라.

스프링을 가지런히 정리하는 함수 Reorder(N)을 작성해야 한다. Reorder(N) 함수는 springboard.c 또는 springboard.cpp에 있다.

void Reorder(int N) 함수의 인자는 다음과 같다.

• $N$: 스프링의 개수 ($1 \le N \le 12\,345$)

Reorder 함수 안에서 PutBall(K)을 여러 번 호출할 수 있다.

int PutBall(int K)는 왼쪽에서 K번째 스프링에 공을 떨어뜨린다.

• $K$: 공을 놓는 위치 ($1 \le K \le N$)
• 반환값: 공이 왼쪽으로 나가면 -1, 오른쪽으로 나가면 1을 반환한다.

Reorder(N) 함수가 끝났을 때 모든 스프링이 왼쪽을 보고 있어야 한다. 그렇지 않으면 채점 프로그램이 Wrong[1]을 출력한다. 인자가 범위를 벗어나면 Wrong[2]를 출력하고 즉시 끝난다. PutBall(K)을 허용된 횟수를 넘겨 호출하면 Wrong[3]을 출력하고 즉시 끝난다.

PutBall(K) 함수는 최대 $16$번 호출할 수 있다.

채점 프로그램은 Reorder 함수를 호출하기 전에 초기 스프링 배치를 고정하며, 호출 결과에 따라 배치를 바꾸지 않는다(Non-Adaptive). 메모리 접근, 시스템 호출 등 비정상적인 방법을 쓰면 오답 처리될 수 있다.

예시 프로그램은 다음과 같다. 주석은 같은 상황에서 함수의 반환값을 뜻한다.

#include "springboard.h"

void Reorder(int N) {
	PutBall(3); // 반환값 = -1
	PutBall(1); // 반환값 = 1
}

문제 페이지에서 샘플 코드를 다운로드할 수 있다. Visual Studio, Eclipse, Code::Blocks 같은 IDE를 쓴다면 springboard.cpp, springboard.h, grader.cpp(또는 springboard.c, springboard.h, grader.c)를 한 프로젝트에 넣어 컴파일하면 된다. 터미널에서 컴파일하려면 아래 명령어를 쓰면 된다.

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

프로그램을 실행하면 표준입력으로 N과 N개 스프링의 방향을 입력받는다. 방향은 'L' 또는 'R'로 이루어진 길이 N의 문자열이며, 'L'은 왼쪽을 보는 스프링, 'R'은 오른쪽을 보는 스프링을 뜻한다. 모든 정보를 입력받으면 샘플 채점기가 정답 여부를 출력한다.

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