Carlosは夏休みにduplicated binary string（重複二進文字列）について研究している。duplicated binary stringとは、空ではない文字列 $T$ であって、以下の条件を満たすものである。
- $T$ は文字
0と1のみを含む（すなわち、$T$ は二進文字列である）。 - $T$ は $T = \overline{UU}$ という形式で書くことができる。ここで、$U$ は任意の二進文字列であり、演算 $\overline{ab}$ は文字列 $a$ と $b$ の連結（すなわち、一方の文字列の後に他方を続けて一つの文字列とすること）を表す。
例えば、0000 や 011011 は duplicated binary string であるが、01、0110、000 はそうではない。
二進文字列 $S$ の強度 (strength) を、$S$ に含まれる相異なる連続する duplicated substring の数と定義する。2つの部分文字列は、少なくとも1文字でも異なれば別のものとみなす。
この問題は2つのパートで構成されており、各小課題はパートIまたはパートIIに関連付けられている。小課題はどの順序で解いてもよい。特に、パートIIに取り組む前にパートIをすべて完了させる必要はない。
パートI
Carlosはあなたに二進文字列 $S$ を送る。あなたのタスクは、その強度を計算することである。
実装の詳細
以下のプロシージャを実装すること。
int count_duplicated(std::string S)- $S$: 長さ $N$ の二進文字列
- このプロシージャは、各テストケースに対してちょうど1回呼び出される。
このプロシージャは、整数 $K$、すなわち $S$ に含まれる相異なる連続する duplicated substring の数を返す必要がある。
制約
- $4 \le N \le 100$
- $0 \le i < N$ を満たすすべての $i$ について、$S[i]$ は
0または1である。
小課題
| 小課題 | 配点 | 制約 |
|---|---|---|
| 1 | 6 | $N = 4$ |
| 2 | 9 | 追加の制約なし |
入出力例
入出力例 1
count_duplicated("0101")$S$ に含まれる duplicated binary substring は 0101 の1つだけである。したがって、このプロシージャは 1 を返す必要がある。
入出力例 2
count_duplicated("0000")$S$ に含まれる duplicated binary substring は 00 と 0000 の2つである。したがって、このプロシージャは 2 を返す必要がある。
注記：部分文字列 00 は $S$ 内に3回出現するが、最終的な答えでは1回のみカウントされることに注意せよ。
パートII
Carlosは、二進文字列 $S$ の強度の最小値と最大値がいくつになるか疑問に思っている。
あなたのタスクは、長さ100の二進文字列を構築し、duplicated substring をできるだけ少なく、あるいは多く含めることである。duplicated substring の数に基づいてスコアが与えられる。
小課題
このパートは、部分点のある2つの出力専用小課題で構成されている。
| 小課題 | 配点 | 制約 |
|---|---|---|
| 3 | 25 | $S$ の強度を最小化する |
| 4 | 60 | $S$ の強度を最大化する |
実装の詳細
各小課題について、以下のいずれかを行う必要がある。
- 長さ100の二進文字列からなる出力ファイルを提出する。
- プログラム内で grader プロシージャの呼び出しに対して二進文字列を返す。
各出力ファイルは以下の形式でなければならない。
S
あなたのプログラム内で必要な二進文字列を構築するために、以下のプロシージャを実装すること。
std::string find_weakest()- 提出物に小課題3の出力ファイルが含まれている場合、このプロシージャは呼び出されない。
- それ以外の場合、このプロシージャは小課題3においてちょうど1回呼び出される。
このプロシージャは、強度を最小化する長さ $N = 100$ の二進文字列 $S$ を返す必要がある。
std::string find_strongest()- 提出物に小課題4の出力ファイルが含まれている場合、このプロシージャは呼び出されない。
- それ以外の場合、このプロシージャは小課題4においてちょうど1回呼び出される。
このプロシージャは、強度を最大化する長さ $N = 100$ の二進文字列 $S$ を返す必要がある。
注記
もしあなたの出力が実装の詳細で説明されている制約に従っていない場合、その小課題のスコアは0点となる（CMSでは Output isn't correct と報告される）。
与えられた小課題におけるあなたの出力の強度を $K$ とする。
小課題3では、スコアは以下の表に従って計算される。
| 条件 | 配点 |
|---|---|
| $20 < K$ | 0 |
| $4 < K \le 20$ | $21 - K$ |
| $K = 4$ | 20 |
| $K = 3$ | 25 |
小課題4では、スコアは以下の表に従って計算される。
| 条件 | 配点 |
|---|---|
| $K \le 50$ | 0 |
| $50 < K \le 80$ | $K - 50$ |
| $80 < K \le 83$ | $30 + 5 \cdot (K - 80)$ |
| $K = 84$ | 60 |
入出力例
パートIおよびIIは同じサンプル grader プログラムを使用し、入力の最初の行によって両パートが区別される。
入力形式（パートI）
1 S
出力形式（パートI）
K
入力形式（パートII）
2 T
ここで、$T$ は文字列 weakest または strongest である。
出力形式（パートII）
S
サンプル grader の出力は、パートIIの出力ファイルに必要な形式に従っていることに注意せよ。