| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 36 | 2 | 2 | 22.222% |
Carlos spends his summer holiday studying duplicated binary strings. A duplicated binary string is a non-empty string $T$ such that:
0 and 1 (that is, $T$ is a binary string).For example, 0000 and 011011 are duplicated binary strings, but 01, 0110, and 000 are not.
Define the strength of a binary string $S$ as the number of distinct contiguous duplicated substrings present in $S$. Two substrings are considered different if they differ in at least one character.
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.
Carlos sends you a binary string $S$, and your task is to calculate its strength.
You should implement the following procedure.
int count_duplicated(std::string S)
The procedure should return an integer $K$, the number of distinct contiguous duplicated substrings present in $S$.
0 or 1 for each $i$ such that $0 ≤ i < N$.| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $N = 4$ |
| 2 | 9 | No additional constraints. |
Example 1
Consider the following call.
count_duplicated("0101")
There is only one duplicated binary substring in $S$, which is 0101. Therefore the procedure should return $1$.
Example 2
Consider the following call.
count_duplicated("0000")
There are two duplicated binary substrings in $S$: 00 and 0000. Hence, the procedure should return $2$.
Note that although the substring 00 appears three times in $S$, it is counted only once in the final answer.
Carlos wonders what the minimum and maximum strength of a binary string $S$ can be.
Your task is to construct binary strings of length $100$ that contain as few or as many duplicated substrings as possible. You will receive a score based on the number of duplicated substrings.
| 번호 | 배점 | 제한 |
|---|---|---|
| 3 | 25 | Minimize the strength of $S$. |
| 4 | 60 | Maximize the strength of $S$. |
For each subtask, you should return a binary string in your program to a grader procedure call.
To construct the required binary strings in your solution program, you should implement the following procedures.
std::string find_weakest()
The procedure should return a binary string $S$ of length $N = 100$ with minimum strength.
std::string find_strongest()
The procedure is called in Subtask 4 exactly once.
The procedure should return a binary string $S$ of length $N = 100$ with maximum strength.
If your output does not conform to the constraints described in the implementation details, the score of your solution for that subtask will be $0$.
Let $K$ denote the strength of the string in your output for a given subtask.
In Subtask 3, your score is calculated according to the following table:
| Condition | Points |
|---|---|
| $20 < K$ | $0$ |
| $4 < K ≤ 20$ | $21 − K$ |
| $K = 4$ | $20$ |
| $K = 3$ | $25$ |
In Subtask 4, your score is calculated according to the following table:
| Condition | Points |
|---|---|
| $K ≤ 50$ | $0$ |
| $50 < K ≤ 80$ | $K − 50$ |
| $80 < K ≤ 83$ | $30 + 5 \cdot (K − 80)$ |
| $K = 84$ | $60$ |
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 S
Output format for Part I:
K
Input format for Part II:
2 T
Here, T is either the string weakest or the string strongest.
Output format for Part II:
S
Note that the output of the sample grader adheres to the required format for the output files in Part II.
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)