Carlos 正在利用暑假研究「重複二元字串」。一個重複二元字串是一個非空的字串 $T$，滿足以下條件：

• $T$ 僅包含字元 $0$ 和 $1$（亦即 $T$ 是一個二元字串）。
• $T$ 可以寫成 $T = \overline{UU}$ 的形式，其中 $U$ 為任意二元字串，而運算 $\overline{ab}$ 代表字串 $a$ 與 $b$ 的串接（即將它們一個接一個寫成單一字串）。

例如，$0000$ 和 $011011$ 是重複二元字串，但 $01$、$0110$ 和 $000$ 則不是。

定義二元字串 $S$ 的「強度」（strength）為 $S$ 中存在的相異連續重複子字串的數量。若兩個子字串在至少一個字元上不同，則視為不同的子字串。

本題包含兩個部分，每個子任務與 Part I 或 Part II 相關。你可以按任意順序解決子任務；特別地，你不必在嘗試 Part II 之前完成 Part I 的所有內容。

Part I

Carlos 給你一個二元字串 $S$，你的任務是計算它的強度。

實作細節

你應該實作以下函式：

int count_duplicated(std::string S)

• $S$: 長度為 $N$ 的二元字串。
• 此函式對每個測試案例僅會被呼叫一次。

此函式應回傳一個整數 $K$，即 $S$ 中存在的相異連續重複子字串的數量。

資料範圍

• $4 \le N \le 100$
• 對於每個 $0 \le i < N$，$S[i]$ 為 $0$ 或 $1$。

子任務

範例

範例 1

考慮以下呼叫：

count_duplicated("0101")

$S$ 中只有一個重複二元子字串，即 $0101$。因此，該函式應回傳 $1$。

範例 2

考慮以下呼叫：

count_duplicated("0000")

$S$ 中有兩個重複二元子字串：$00$ 和 $0000$。因此，該函式應回傳 $2$。

注意，儘管子字串 $00$ 在 $S$ 中出現了三次，但在最終答案中它只被計算一次。

Part II

Carlos 想知道二元字串 $S$ 的最小強度與最大強度分別為何。

你的任務是構造長度為 $100$ 的二元字串，使其包含盡可能少或盡可能多的重複子字串。你將根據重複子字串的數量獲得分數。

子任務

本部分包含 2 個僅輸出（output-only）的子任務，採用部分給分。

實作細節

對於每個子任務，你應該：

• 提交一個包含長度為 $100$ 的二元字串的輸出檔案，或者
• 在你的程式中回傳一個二元字串給評測系統的函式呼叫。

每個輸出檔案必須採用以下格式：

S

若要在你的解決方案程式中構造所需的二元字串，你應該實作以下函式：

std::string find_weakest()

• 若你的提交中提供了子任務 3 的輸出檔案，則不會呼叫此函式。
• 否則，此函式在子任務 3 中會被呼叫一次。

此函式應回傳一個長度為 $N = 100$ 且強度最小的二元字串 $S$。

std::string find_strongest()

• 若你的提交中提供了子任務 4 的輸出檔案，則不會呼叫此函式。
• 否則，此函式在子任務 4 中會被呼叫一次。

此函式應回傳一個長度為 $N = 100$ 且強度最大的二元字串 $S$。

評分

如果你的輸出不符合實作細節中描述的限制，該子任務的得分將為 $0$（在 CMS 中顯示為 Output isn't correct）。

令 $K$ 為給定子任務中你輸出字串的強度。

在子任務 3 中，你的得分根據下表計算：

在子任務 4 中，你的得分根據下表計算：

範例評測程式

Part I 和 Part II 使用相同的範例評測程式，兩部分的區別由輸入的第一行決定。

輸入格式 (Part I)

1
S

輸出格式 (Part I)

K

輸入格式 (Part II)

2
T

此處 $T$ 為字串 weakest 或 strongest。

輸出格式 (Part II)

S

注意，範例評測程式的輸出符合 Part II 輸出檔案所需的格式。