Карлос проводит летние каникулы, изучая дублированные бинарные строки. Дублированная бинарная строка — это непустая строка $T$ такая, что:

• $T$ содержит только символы 0 и 1 (то есть $T$ является бинарной строкой).
• $T$ может быть записана в виде $T = \overline{UU}$, где $U$ — произвольная бинарная строка, а операция $\overline{ab}$ обозначает конкатенацию строк $a$ и $b$ (то есть запись их друг за другом как одной строки).

Например, 0000 и 011011 являются дублированными бинарными строками, а 01, 0110 и 000 — нет.

Определим силу бинарной строки $S$ как количество различных непрерывных дублированных подстрок, присутствующих в $S$. Две подстроки считаются различными, если они различаются хотя бы одним символом.

Эта задача состоит из двух частей, каждая подзадача относится либо к Части I, либо к Части II. Вы можете решать подзадачи в любом порядке; в частности, вам не обязательно полностью выполнять Часть I перед тем, как приступать к Части II.

Часть I

Карлос присылает вам бинарную строку $S$, и ваша задача — вычислить её силу.

Детали реализации

Вы должны реализовать следующую процедуру:

int count_duplicated(std::string S)

• $S$: бинарная строка длины $N$.
• Эта процедура вызывается ровно один раз для каждого тестового примера.

Процедура должна вернуть целое число $K$ — количество различных непрерывных дублированных подстрок, присутствующих в $S$.

Ограничения

• $4 \le N \le 100$
• $S[i]$ является либо 0, либо 1 для каждого $i$ такого, что $0 \le i < N$.

Подзадачи

Примеры

Пример 1

Рассмотрим следующий вызов:

count_duplicated("0101")

В $S$ есть только одна дублированная бинарная подстрока, это 0101. Поэтому процедура должна вернуть 1.

Пример 2

Рассмотрим следующий вызов:

count_duplicated("0000")

В $S$ есть две дублированные бинарные подстроки: 00 и 0000. Следовательно, процедура должна вернуть 2.

Примечание: хотя подстрока 00 встречается в $S$ три раза, в итоговом ответе она учитывается только один раз.

Часть II

Карлос задается вопросом, какими могут быть минимальная и максимальная сила бинарной строки $S$.

Ваша задача — сконструировать бинарные строки длины 100, которые содержат как можно меньше или как можно больше дублированных подстрок. Вы получите баллы в зависимости от количества дублированных подстрок.

Подзадачи

Эта часть состоит из 2 подзадач с выводом в файл (output-only) и частичным оцениванием.

Детали реализации

Для каждой подзадачи вы должны либо: отправить выходной файл, состоящий из бинарной строки длины 100, либо вернуть бинарную строку в вашей программе при вызове процедуры проверяющей системы.

Каждый выходной файл должен быть в следующем формате:

S

Чтобы сконструировать требуемые бинарные строки в вашей программе, вы должны реализовать следующие процедуры:

std::string find_weakest()

• Если в вашей посылке предоставлен выходной файл для Подзадачи 3, эта процедура вызываться не будет.
• В противном случае процедура вызывается в Подзадаче 3 ровно один раз.

Процедура должна вернуть бинарную строку $S$ длины $N = 100$ с минимальной силой.

std::string find_strongest()

• Если в вашей посылке предоставлен выходной файл для Подзадачи 4, эта процедура вызываться не будет.
• В противном случае процедура вызывается в Подзадаче 4 ровно один раз.

Процедура должна вернуть бинарную строку $S$ длины $N = 100$ с максимальной силой.

Оценивание

Если ваш вывод не соответствует ограничениям, описанным в деталях реализации, балл за эту подзадачу будет равен 0 (в CMS будет отображено как Output isn't correct).

Пусть $K$ обозначает силу строки в вашем выводе для данной подзадачи.

В Подзадаче 3 ваш балл рассчитывается согласно следующей таблице:

В Подзадаче 4 ваш балл рассчитывается согласно следующей таблице:

Примеры

Пример 1 (Входные данные для Части I)

1
S

Пример 2 (Выходные данные для Части I)

K

Пример 3 (Входные данные для Части II)

2
T

Здесь $T$ — это либо строка weakest, либо строка strongest.

Пример 4 (Выходные данные для Части II)

S

Примечание: вывод примера проверяющей системы соответствует требуемому формату для выходных файлов в Части II.