비밀 Batch 컴파일 명령

승현이는 비밀스러운 이항 연산자 $\star$를 만들었습니다. 1,000,000,000 이하의 두 음이 아닌 정수 $x$, $y$에 대해, 1,000,000,000 이하인 음이 아닌 정수 $x \star y$는 유일하게 결정됩니다. $\star$ 연산자는 결합법칙이 성립합니다. 즉, 1,000,000,000 이하의 음이 아닌 정수들 $x, y, z$에 대해 등식 $(x \star y) \star z = x \star (y \star z)$가 성립합니다. 이 값은 단순히 $x \star y \star z$로 표현됩니다.

승현이는 지학이와 게임을 할 계획을 세웠습니다. 승현이는 지학이에게 연산자 $\star$가 무엇인지 추측해 보라고 했습니다. 승현이는 지학이에게 $N$개의 정수들 $A_{0}, A_{1}, \cdots, A_{N-1}$을 보여주더니, 지학이에게 다음과 같은 형태의 질의를 많이 던져줬습니다: "$A_{L} \star A_{L+1} \star \cdots \star A_{R}$의 값이 뭐니??"

지학이는 힌트 없이는 너무 어렵다고 말했습니다. 따라서 승현이는 지학이에게 힌트를 좀 주기로 했습니다. 각 힌트는 다음과 같이 주어집니다: 지학이는 두 개의 정수 $x, y$를 선택해서 승현이에게 $x \star y$의 값을 물어볼 것이고, 승현이는 지학이에게 $x \star y$의 값을 알려줄 것입니다. 지학이는 게임 초반에 $A_{0}, A_{1}, \cdots, A_{N-1}$이 주어질 때 힌트들을 요청할 수 있습니다. 물론, 지학이는 힌트의 수를 줄이고 싶어합니다. 지학이는 마치 자기가 $\star$ 연산자에 대해서 아는 양 행동하고 싶어하기에, 자신에게 질의가 주어진 후에는 특히 힌트를 덜 요청하고자 합니다.

해야 할 일

지학이가 힌트를 요청하고 승현이의 질문에 답할 최적의 전략을 구현하세요.

구현 세부사항

여러분은 힌트를 요청하고 승현이의 질의들에 답변하는 전략을 구현한 프로그램을 작성해야 합니다. 여러분의 프로그램은 #include "secret.h"를 통해 헤더 파일 secret.h를 포함해야 합니다.

여러분은 다음 프로시저들을 구현해야 합니다.

• void Init (int N, int A[])
  이 프로시저는 처음에 단 한 번 호출됩니다. 파라미터 N은 승현이가 지학이에게 보여준 정수들의 개수 $N$입니다. 파라미터 A는 길이가 $N$인 배열입니다. 원소들 A[0], A[1], …, A[N-1]은 승현이가 보여준 정수들 $A_{0}, A_{1}, \cdots, A_{N-1}$입니다.
• int Query (int L, int R)
  이 프로시저는 승현이가 지학이에게 질의를 줄 때 호출됩니다. 이것은 승현이가 지학이에게 $A_{L} \star A_{L+1} \star \cdots \star A_{R}$ ($0 \le L \le R \le N-1$)의 값을 물어보고 있다는 것입니다.
  이 프로시저는 $A_{L} \star A_{L+1} \star \cdots \star A_{R}$의 값을 반환해야 합니다.

다음 프로시저는 여러분의 프로그램에 의해 호출될 수 있습니다.

• int Secret (int X, int Y)
  이 함수는 지학이가 힌트를 요청할 때 호출됩니다. 이것은 지학이가 $X \star Y$의 값을 물어보고 있다는 것을 의미합니다. 파라미터 X와 Y는 $0 \le X \le 1,000,000,000$과 $0 \le Y \le 1,000,000,000$을 만족하는 정수들 $X$와 $Y$여야 합니다. 만약 이 프로시저가 위 조건을 만족하지 않도록 호출된다면, 여러분의 프로그램은 Wrong Answer [1] 판정을 받으며 즉시 종료됩니다.
  이 프로시저는 $X \star Y$의 값을 반환합니다.

컴파일 및 시험 실행

여러분은 여기에서 예시 그레이더를 내려받아서 여러분의 프로그램을 시험할 수 있습니다. 이 압축 파일은 여러분이 작성해야 할 프로그램의 예시 역시 포함하고 있습니다.

예시 그레이더는 grader.c또는 grader.cpp 중에 하나인 소스 코드 하나를 포함하고 있습니다. 예를 들어, 만약 여러분의 프로그램이 secret.c 또는 secret.cpp라면, 여러분은 여러분의 프로그램을 컴파일하기 위해 다음 명령을 실행해야 합니다.

• C : gcc -O2 -std=c11 -o grader grader.c secret.c -lm
• C++ : g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp

만약 컴파일에 성공했다면, 실행 가능한 파일 grader가 생성됩니다.

실제 그레이더는 예시 그레이더와는 다르다는 것을 명심하세요. 예시 그레이더는 표준 입력에서 데이터를 읽어서 표준 출력에 결과를 출력하는 하나의 프로그램으로서 실행될 것입니다.

예시 그레이더의 설명서

예시 그레이더는 승현이의 비밀스러운 이항 연산자 $\star$가 $x \star y = \min{x + 2 \lfloor \frac{y}{2} \rfloor, 1 000 000 000}$이라고 가정합니다. 여기서 $\lfloor r \rfloor$는 $r$ 이하의 가장 큰 정수를 나타냅니다. 이것은 실제 그레이더와는 다르다는 것을 참고하세요.

예시 그레이더의 입력 형식

예시 그레이더는 아래에 명시한 대로 데이터를 표준 입력에서 읽습니다.

• 첫 번째 줄에 승현이가 지학이에게 보여 준 정수들의 수 $N$이 주어집니다.
• 두 번째 줄에 승현이가 지학이에게 보여준 정수들 $A_{0}, A_{1}, \cdots, A_{N-1}$이 공백을 사이로 두고 주어집니다.
• 세 번째 줄에 승현이가 지학이에게 준 질의의 수 $Q$가 주어집니다.
• 다음 $Q$개 줄 중에서 $(j+1)$번째 줄 ($0 \le j \le Q-1$)에는 두 개의 정수 $L_{j}$와 $R_{j}$ ($0 \le L_{j} \le R_{j} \le N-1$)이 공백을 사이로 두고 주어집니다. 이는 승현이가 $(j+1)$번째 질의에서 $A_{L_{j}} \star A_{L_{j}+1} \star \cdots \star A_{R_{j}}$의 값을 요청한다는 것을 의미합니다.

예시 그레이더의 출력 형식

프로그램이 성공적으로 종료된다면, 예시 그레이더는 Query 함수에 의해 반환된 값들을 한 줄에 하나씩 차례대로 표준 출력에 출력합니다. 그레이더는 또한 표준 출력에 다음 정보를 출력합니다.

• 만약 여러분의 프로그램이 Wrong Answer [1] 판정을 받았다면, 그레이더는 "Wrong Answer [1]" (따음표 제외)를 출력합니다.
• 만약 여러분의 프로그램이 Wrong Answer [1] 판정을 받지 않았다면, 그레이더는 Init 함수에서 Secret를 호출한 횟수와, Query 함수를 한 번 호출했을 때 이 함수에서 Secret를 호출한 횟수 중 최댓값을 출력합니다.

제약 조건

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

• $1 \le N \le 1,000$
• $0 \le A_{i} \le 1,000,000,000$ ($0 \le i \le N-1$)
• Query의 호출 횟수는 10 000회 이하입니다.

채점 방식

만약 여러분의 프로그램이 모든 테스트 케이스에서 성공적으로 종료되었고, Wrong Answer [1] 판정을 받지 않았고, 정확한 값을 반환했다면 점수가 주어집니다.

1. 모든 테스트 케이스에서 아래 조건을 만족했다면 100점입니다.
   • Init에서, Secret 함수를 호출한 횟수는 8 000회 이하여야 합니다.
   • Query를 호출할 떄마다 Secret을 호출환 횟수는 1회 이하여야 합니다.
2. 모든 테스트 케이스에서 1의 조건을 만족하지 않고 아래 조건을 만족한다면 30점입니다.
   • Init에서, Secret 함수를 호출한 횟수는 8 000회 이하여야 합니다.
   • Query를 호출할 떄마다 Secret을 호출환 횟수는 20회 이하여야 합니다.
3. 1의 조건 또는 2의 조건을 만족하지 않을 시 6점입니다.

예시 상호 작용

8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4

Call	Return
Init(8, [1, 4, 7, 2, 5, 8, 3, 6])	None
Query(0, 3)	13
Query(1, 7)	32
Query(5, 5)	8
Query(2, 4)	13

함수 Secret은 함수 Init 또는 함수 Query에서 호출될 수 있습니다. 예를 들어, 만약 Secret(4, 7)이 호출되었다면 반환값은 10입니다. 예시 그레이더가 사용한 연산자에서 $4 \star 7 = 10$이기 때문입니다.

첫 번째 질의에서 $1 \star 4 \star 7 \star 2$의 값이 요청되었습니다.

$$1 \star 4 \star 7 \star 2 = (1 \star (4 \star7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13$$

이므로, 이 때 함수 Query는 13을 반환해야 합니다.