비밀 Batch 컴파일 명령
시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
---|---|---|---|---|
20000 ms | 512 MiB | 1828 | 441 | 24.12% |
승현이는 비밀스러운 이항 연산자 $\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] 판정을 받지 않았고, 정확한 값을 반환했다면 점수가 주어집니다.
- 모든 테스트 케이스에서 아래 조건을 만족했다면 100점입니다.
Init
에서,Secret
함수를 호출한 횟수는 8 000회 이하여야 합니다.Query
를 호출할 떄마다Secret
을 호출환 횟수는 1회 이하여야 합니다.
- 모든 테스트 케이스에서 1의 조건을 만족하지 않고 아래 조건을 만족한다면 30점입니다.
Init
에서,Secret
함수를 호출한 횟수는 8 000회 이하여야 합니다.Query
를 호출할 떄마다Secret
을 호출환 횟수는 20회 이하여야 합니다.
- 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을 반환해야 합니다.
파일명 | 파일 크기 |
---|---|
secret.zip | 2.9 KiB |