질문 Interactive 컴파일 명령

참고: 대회에서 채점기 등을 제공하지 않은 관계로 임의로 채점기를 작성했습니다. 따라서 문제 서술이 실제와 약간 다릅니다만, 요지는 같습니다.

지학이와 상수는 최고 기밀의 연구소에 침입하고자 합니다. 불운하게도, 입구는 정교한 보안 시스템을 갖추고 있습니다. 이 시스템은 반드시 "예" 또는 "아니오"로 답해야 하는 질문 ("편의상" 정수 $q$ ($1 \le q \le N$)로 부호화되는) 을 합니다. 만약 답이 정확하다면 시스템은 문을 열어 주지만, 그렇지 않다면 알람이 울립니다.

지학이와 상수 모두 시스템이 하는 질문 $q$가 항상 $x$과 같거나 $y$와 같다 ($x \neq y$)는 사실을 알고 있습니다. 이 때 질문 $x$에 대한 정확한 답은 "예"이고, 질문 $y$에 대한 정확한 답은 "아니오"입니다.

하지만, 지학이와 상수가 그들의 침입을 상세하게 계획하는 동안, 그들은 $x$와 $y$의 값을 기억할 수 없습니다. 따라서, 상수는 질문에 답하기 위해 입구로 보내졌고, 지학이는 탈출을 보장하기 위해 거리를 두고 서 있습니다.

그런데, 갑자기 질문 $q$가 등장하자, 지학이는 $x$와 $y$의 값과 정확한 답들을 기억해냈습니다. 그러나 지학이와 상수의 거리가 꽤 멀기 때문에 지학이는 상수에게 어떤 답을 외칠지 분명하게 지시할 수 없습니다. 지학이는 상수에게 단지 한 개의 정수 $h$ ($1 \le h$)만을 외칠 수 있습니다. 따라서, 지학이는 상수가 질문에 정확히 대답하기 위해 필요한 모든 정보를 $h$ 안에 담아야 합니다.

이러한 상황에 처한 지학이와 상수를 도와 각각의 역할을 하는 프로그램을 작성해 주세요.

구현

여러분은 같은 프로그래밍 언어로 두 개의 분리된 프로그램을 작성해야 합니다. 이 프로그램들은 채점 과정에서 서로 통신되지 않고, 독립적으로 실행되며, 순서대로 실행됩니다.

첫 번째 프로그램은 지학이의 역할을 합니다. 여러분은 이 프로그램에서 encode(N, x, y) 함수를 구현해야 합니다. 이 함수는 $N, x, y$의 값을 파라미터로 받아서, 지학이가 상수에게 외쳐야 할 정수 $h$을 반환해야 합니다.

두 번째 프로그램은 상수의 역할을 합니다. 여러분은 이 프로그램에서 decode(N, q, h) 함수를 구현해야 합니다. 이 함수는 $N, q, h$의 값을 파라미터로 받아서 상수가 어떤 답을 골라야 할 지를 반환해야 합니다. 만약 "예"를 답해야 한다면 1을, "아니오"를 답해야 한다면 0을 반환하면 됩니다.

예제 채점기

여러분의 구현을 돕기 위하여 예제 채점기가 제공됩니다. 이 채점기는 여러분이 구현한 두 개의 소스 코드를 동시에 실행하며, 실제 채점 시에는 이 채점기가 사용되지 않습니다. 여러분은 grader.c(pp), encode.c(pp), decode.c(pp)를 한꺼번에 컴파일하시면 됩니다.

예제 채점기는 아래 입력을 표준 입력(stdin)으로부터 받습니다:

• 첫 번째 줄: $N$과 테스트 케이스의 수 $T$
• 다음 $T$개 줄: $x, y, q$

예를 들어, 아래와 같이 입력할 수 있습니다.

5 6
1 2 1
4 5 4
1 2 2
3 5 3
4 5 5
5 2 2

예제 채점기는 실행 결과를 표준 출력(stdout)에 출력합니다.

제약 조건

모든 테스트 케이스에서 $1 \le N \le 920$, $1 \le T \le 2,000,000$

채점

여러분의 점수는 지학이가 상수에게 외친 $h$들 중 가장 큰 값에 따라서 결정됩니다.

또한, 여러분의 프로그램은 모든 테스트 케이스에 대해 정확하게 답해야 합니다. 그렇지 않는다면 0점을 받습니다.