| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 48 | 4 | 4 | 40.000% |
The Cordillera Oriental is a mountain range in the Andes that stretches across Bolivia. It consists of a sequence of $N$ mountain peaks, numbered from $0$ to $N - 1$. The height of peak $i$ ($0 \leq i < N$) is $H[i]$, which is an integer between $1$ and $N - 1$, inclusive.
For any two peaks $i$ and $j$ where $0 \leq i < j < N$, the distance between them is defined as $d(i, j) = j - i$.
According to ancient Inca legends, a triple of peaks is mythical if it has the following special property: the heights of the three peaks match their pairwise distances ignoring the order.
Formally, a triple of indices $(i, j, k)$ is mythical if
This problem consists of two parts, with each subtask associated with either Part I or Part II. You may solve the subtasks in any order. In particular, you are not required to complete all of Part I before attempting Part II.
Given a description of the mountain range, your task is to count the number of mythical triples.
You should implement the following procedure.
long long count_triples(std::vector<int> H)
The procedure should return an integer $T$, the number of mythical triples in the mountain range.
Part I is worth a total of $70$ points.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $N \leq 100$ |
| 2 | 6 | $H[i] \leq 10$ for each $i$ such that $0 \leq i < N$. |
| 3 | 10 | $N \leq 2000$ |
| 4 | 11 | The heights are non-decreasing. That is, $H[i - 1] \leq H[i]$ for each $i$ such that $1 \leq i < N$. |
| 5 | 16 | $N \leq 50\,000$ |
| 6 | 19 | No additional constraints. |
Consider the following call.
count_triples([4, 1, 4, 3, 2, 6, 1])
There are $3$ mythical triples in the mountain range:
Hence, the procedure should return $3$.
Note that the indices $(0, 2, 4)$ do not form a mythical triple, as the heights $(4,4,2)$ do not match the pairwise distances $(2,4,2)$.
Your task is to construct mountain ranges with many mythical triples. This part consists of $6$ output-only subtasks with partial scoring.
In each subtask, you are given two positive integers $M$ and $K$, and you should construct a mountain range with at most$M$ peaks. If your solution contains at least $K$ mythical triples, you will receive the full score for this subtask. Otherwise, your score will be proportional to the number of mythical triples your solution contains.
Note that your solution must consist of a valid mountain range. Specifically, suppose your solution has $N$ peaks ($N$ must satisfy $3 \leq N \leq M$). Then, the height of peak $i$ ($0 \leq i < N$), denoted by $H[i]$, must be an integer between $1$ and $N - 1$, inclusive.
There is one method to submit your solution, and you may use it for each subtask:
To submit your solution via a procedure call, you should implement the following procedure.
std::vector<int> construct_range(int M, int K)
The procedure should return an array $H$ of length $N$, representing the heights of the peaks.
Part II is worth a total of $30$ points. For each subtask, the values of $M$ and $K$ are fixed and given in the following table:
| 번호 | 배점 | $M$ | $K$ |
|---|---|---|---|
| 7 | 5 | $20$ | $30$ |
| 8 | 5 | $500$ | $2000$ |
| 9 | 5 | $5000$ | $50\,000$ |
| 10 | 5 | $30\,000$ | $700\,000$ |
| 11 | 5 | $100\,000$ | $2\,000\,000$ |
| 12 | 5 | $200\,000$ | $12\,000\,000$ |
For each subtask, if your solution does not form a valid mountain range, your score will be $0$ (reported as Output isn't correct in CMS).
Otherwise, let $T$ denote the number of mythical triples in your solution. Then, your score for the subtask is: $$5 \cdot \min\left(1,\frac{T}{K}\right).$$
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | |
| 2 | 6 | |
| 3 | 10 | |
| 4 | 11 | |
| 5 | 16 | |
| 6 | 19 | |
| 7 | 5 | |
| 8 | 5 | |
| 9 | 5 | |
| 10 | 5 | |
| 11 | 5 | |
| 12 | 5 |
Parts I and II use the same sample grader program, with the distinction between the two parts determined by the first line of the input.
Input format for Part I:
1
N
H[0] H[1] ... H[N-1]
Output format for Part I:
T
Input format for Part II:
2
M K
Output format for Part II:
N
H[0] H[1] ... H[N-1]
Note that the output of the sample grader matches the required format for the output file in Part II.
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)