34211번 - Duplicated Binary Strings 서브태스크점수다국어언어 제한함수 구현

문제

Carlos spends his summer holiday studying duplicated binary strings. A duplicated binary string is a non-empty string $T$ such that:

• $T$ contains only the characters 0 and 1 (that is, $T$ is a binary string).
• $T$ can be written in the form $T = \overline{UU},ドル where $U$ is an arbitrary binary string and the operation $\overline{ab}$ denotes the concatenation of the strings $a$ and $b$ (i.e., writing them one after the other as a single 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.

입력

출력

제한

Part I

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)

• $S$: binary string of length $N$
• This procedure is called exactly once for each test case.

The procedure should return an integer $K,ドル the number of distinct contiguous duplicated substrings present in $S$.

제한

• 4ドル ≤ N ≤ 100$
• $S[i]$ is either 0 or 1 for each $i$ such that 0ドル ≤ i < N$.

서브태스크

예제

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.

Part II

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.

서브태스크

구현 상세

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 is called in Subtask 3 exactly once.

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:

In Subtask 4, your score is calculated according to the following table:

서브태스크

힌트

샘플 그레이더

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.

첨부

• bitstrings.zip