라멘 Batch Compilation commands

승현이와 상수는 라멘을 좋아합니다. 승현이는 담백한 라멘을 좋아하는 반면 상수는 걸죽한 라멘을 좋아합니다. 서울에는 $0$번부터 $N-1$번까지 총 $N$채의 라멘 가게가 있습니다.

이 둘은 어느 라멘 가게에서 걸죽한 라멘을 만드는지, 또 어느 라멘 가게에서 담백한 라멘을 만드는지 모릅니다. 그래서 승현이와 상수는 동네의 라멘 가게들 중에서 가장 담백한 라멘을 제공하는 가게와 가장 걸죽한 라멘을 제공하는 가게가 어디인지를 결정하기로 했습니다.

서울의 라멘 가게들에는 각 가게에서 제공되는 라면의 진한 정도가 정해져 있습니다. 이 진한 정도는 $0$ 이상 $N - 1$ 이하의 정수이며, 각 라면 가게마다의 진한 정도는 서로 다릅니다. 승현이와 상수는 하루에 두 개의 라면 가게에 방문하고 맛을 비교하여 두 라멘 가게 중 어느 집이 진한 정도가 더 높은지를 판정할 수 있습니다.

건강을 위해 승현이와 상수는 이렇게 라멘을 먹고 비교하는 일을 600일까지만 하고자 합니다.

해야 할 일

마을에 있는 라면 가게의 수 $N$이 주어질 때, 최대 600일 동안 라멘을 먹고 비교하여 $N$개의 라멘 가게들 중 라면의 진한 정도가 가장 낮은 가게와 가장 높은 가게를 결정하는 프로그램을 작성하세요.

구현 세부 사항

여러분은 진한 정도가 가장 낮은 라면 가게와 진한 정도가 가장 높은 라면 가게를 최대 600번의 비교를 통해 결정하는 방법을 구현한 프로그램을 작성해야 합니다. 프로그램은 아래 함수들을 구현해야 합니다.

• void Ramen (int N)
  • 이 함수는 각 테스트 케이스마다 단 한 번만 호출됩니다. 인수 N은 서울에 있는 라면 가게의 수를 나타냅니다.
  • 여러분은 이 함수에서 Compare를 여러 번 호출하여 진한 정도가 가장 낮은 라면 가게와 가장 높은 라면 가게를 결정하고 Answer를 호출하여 프로그램을 종료해야 합니다.
• int Compare(int X, int Y)
  • 이 함수는 두 라면 가게 중에서 더 진한 라면을 제공하는 가게를 알고자 할 때 호출해야 합니다. 인수 X와 Y는 비교하고자 하는 두 라면 가게의 번호여야 하며, $0$ 이상 $N-1$ 이하의 서로 다른 정수여야만 합니다. 이를 충족하지 않는 인수로 Compare 함수를 호출할 시 **오답 [1]**이 되고, 프로그램은 즉시 종료됩니다.
  • 이 함수는 X번 라면 가게에서 Y번 라면 가게보다 더 진한 라면을 제공한다면 1을 반환하고, 그렇지 않다면 (덜 진한 라면을 제공한다면) -1을 반환합니다.
  • Compare 함수를 600번보다 많이 호출할 시 **오답 [2]**이 되고, 프로그램은 즉시 종료됩니다.

Ramen은 아래 함수를 호출하여 종료해야 합니다. Ramen 함수에서 Answer를 호출하지 않을 시 **오답 [3]**이 되고, 프로그램은 즉시 종료됩니다.

• void Answer(int X, int Y)
  • 이 함수는 Compare 함수들을 적절히 호출하여 가장 진한 라면을 제공하는 라면 가게와 가장 걸죽한(덜 진한) 라면을 제공하는 라면 가게가 정해져 있을 때 호출해야 합니다. X는 가장 덜 진한(걸죽한) 라면을 제공하는 라면 가게의 번호여야 하고, Y는 가장 진한 라면을 제공하는 라면 가게의 번호여야 합니다. X와 Y는 각각 $0$ 이상 $N-1$ 이하의 정수여야 합니다. 이와 맞지 않는 인수로 Answer를 호출하면 **오답 [4]**가 됩니다.
  • Compare 호출의 결과와 모순되지 않는 경우가 유일하고 X와 Y가 이 경우와 같다면 정답입니다. 그렇지 않다면 **오답 [5]**가 됩니다.
  • 이 함수를 호출하면 프로그램이 즉시 종료됩니다.

채점 시 유의사항

평가 시 Compare 호출 결과와 모순되지 않는 경우가 두 가지 이상이라면, 어떤 답을 제시하더라도 **오답 [ERR5]**로 판정됩니다.

채점 중 라면 가게들의 진한 정도가 이전 Compare 호출의 내용에 의해 변화할 수도 있습니다. 이 경우에도 Compare의 결과는 이전의 Compare 호출의 결과와 모순되지는 않습니다.

컴파일 및 실행 방법

작성한 프로그램을 시험해 보기 위한 예시 채점 프로그램은 ramen.zip에서 내려받을 수 있습니다. 이 파일에는 제출해야 할 파일의 예시도 들어 있습니다.

여러분이 작성한 코드를 Ramen.c 또는 Ramen.cpp라고 할 때 작성한 프로그램을 시험하기 위해 다음과 같이 명령을 실행합니다.

• C의 경우 : gcc -O2 -lm grader.c Ramen.c -o grader
• C++의 경우 : g++ -O2 -lm grader.cpp Ramen.cpp -o grader

컴파일에 성공하면 grader라는 실행 파일이 생성됩니다.

실제 채점 프로그램은 주어진 채점 프로그램과 다르다는 점에 유의하세요. 예시 채점 프로그램은 표준 입력에서 입력을 받고 표준 출력에 결과를 출력합니다.

예시 채점 프로그램의 입력 형식

예시 채점 프로그램은 표준 입력(stdin)에서 다음 입력을 받습니다.

• 첫 번째 줄에는 두 개의 정수 $N$과 $T$가 공백을 사이로 두고 주어집니다. $N$은 라면 가게의 수입니다. 예시 채점 프로그램은 $T = 1$인 데이터를 다룹니다.
• $N$개 줄이 주어집니다. 이 중 $i+1$번째 줄 ($0 \le i \le N-1$)에는 정수 $A_{i}$ ($0 \le A_{i} \le N-1$)가 주어집니다. 이것은 $i$번 라면 가게에서 판매하는 라면의 진한 정도를 나타냅니다.

예시 채점 프로그램의 출력 형식

프로그램이 정상적으로 종료된 경우, 예시 채점 프로그램은 표준 출력(stdout)에 아래와 같은 정보를 한 줄에 출력합니다. (따옴표는 출력되지 않습니다)

• 정답인 경우 "Accepted"를 출력합니다.
• 정답이 아닌 경우 "Wrong Answer [2]"와 같이 오답 판정과 그 유형을 같이 출력합니다.

또한 예시 채점 프로그램은 $A_{X} = 0, A_{Y} = N-1$를 만족하는 $X$와 $Y$에 대해 Answer(X, Y)를 호출하면 오답 [5]에 해당하는 경우라도 정답 판정을 내립니다. 이것은 실제 채점 프로그램의 방식과 다르므로 유의하세요.

제약 조건

모든 채점 데이터는 아래 조건을 만족합니다.

• $1 \le N \le 400$

서브태스크

서브태스크 1 [20점]

• $N \le 30$

서브태스크 2 [30점]

• $N \le 300$

서브태스크 3 [50점]

추가적인 제약 조건이 없습니다.

예시

예시 채점 프로그램에 아래와 같이 입력했다고 가정합니다.

3 1
1
2
0

아래와 같이 함수를 호출할 수 있습니다.

함수 호출	반환값
Compare(0,1)	-1
Compare(0,2)	1
Answer(2,1)	프로그램 종료