Time Limit: 1 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
JOI 君と IOI 君は犬を飼うことにした.最初にすべきことは,犬の名前を決めることである.二人で話し合った結果,犬の名前を以下の 4 つの条件を満たすものにすることにした.
条件 1 名前は英大文字 (
A
,B
, ...,Z
) と英小文字 (a
,b
, ...,z
) からなる文字列である.条件 2 JOI 君の好きな文字列は長さ N の文字列 S であるから,S が名前の部分列となるようにする.
条件 3 IOI 君の好きな文字列は長さ M の文字列 T であるから,T が名前の部分列となるようにする.
条件 4 名前を呼びやすいものにするため,同じ文字の間には別の文字が K 文字以上あるようにする.厳密には,位置が異なる任意の同じ文字 2 つについて,必ずその間に別の文字が K 文字以上入っているようにする.なお,K = 0 の場合や,名前の文字がすべて異なる場合は,この条件を満たしていると考える.
ただし,これらの条件では英大文字と英小文字は区別される.例えば
A
とa
は異なる文字とみなされることに注意せよ.
ここで,名前の部分列とは,名前から何文字か (0 文字でもよい) を取り除いて作れる文字列のことである.例えば,名前が algorithm
であるとき,ai
や lgtm
は名前の部分列であるが,joi
や logarithm
は名前の部分列ではない.
二人は名前が短いほど良いと考えているため,4 つの条件のもとで最も短い名前を付けることにした.
JOI 君と IOI 君の好きな文字列および整数 K が与えられたとき,犬に付ける名前の文字数を求めるプログラムを作成せよ.
制約
- 1 \leqq N \leqq 500.
- 1 \leqq M \leqq 500.
- 0 \leqq K \leqq 3.
- S は英大文字と英小文字からなる長さ N の文字列である.
- T は英大文字と英小文字からなる長さ M の文字列である.
- N, M, K は整数である.
小課題
- (2 点) S = T,K = 0.
- (7 点) S = T,K = 1.
- (16 点) S = T.
- (17 点) K = 0.
- (13 点) K = 1,N \leqq 25,M \leqq 25.
- (15 点) K = 1.
- (20 点) K \leqq 2.
- (10 点) 追加の制約はない.
入力
入力は以下の形式で与えられる.
N M K S T
出力
犬に付ける名前の文字数を 1 行で出力せよ.
入力例 1
10 10 0 hottokeiki hottokeiki
出力例 1
10
JOI 君と IOI 君の好きな文字列はどちらも hottokeiki
である.ここで,犬の名前を hottokeiki
にすることを考える.これは以下のように 4 つの条件を満たす.
- 条件 1: 名前は英大文字と英小文字からなる.
- 条件 2: 文字列 S (
hottokeiki
) は犬の名前hottokeiki
の部分列である. - 条件 3: 文字列 T (
hottokeiki
) は犬の名前hottokeiki
の部分列である. - 条件 4: K = 0 なので,この条件は満たしている.
また,これが 4 つの条件を満たす中で最も短い名前である.この文字数 10 を出力する.
この入力例は小課題 1, 3, 4, 7, 8 の制約を満たす.
入力例 2
10 10 1 hottokeiki hottokeiki
出力例 2
11
入力例 1 とは K の値のみが異なる.
もし犬の名前を入力例 1 と同じ hottokeiki
にすれば,条件 4 を満たさない.なぜなら,2 つの t
の間に文字が 1 個もないからである.
4 つの条件を満たす最も短い名前として hotNtokeiki
などが考えられる.この文字数 11 を出力する.
この入力例は小課題 2, 3, 5, 6, 7, 8 の制約を満たす.
入力例 3
10 10 3 hottokeiki hottokeiki
出力例 3
15
入力例 1, 2 とは K の値のみが異なる.
もし犬の名前を入力例 2 と同じ hotNtokeiki
にすれば,条件 4 を満たさない.なぜなら,2 つの t
の間に 1 文字しかなく,2 つの k
の間に 2 文字しかなく,2 つの i
の間に 1 文字しかないからである.
4 つの条件を満たす最も短い名前として hotarutokeiyuki
などが考えられる.この文字数 15 を出力する.
この入力例は小課題 3, 8 の制約を満たす.
入力例 4
6 9 0 Jouhou Orinpikku
出力例 4
14
JOI 君の好きな文字列は Jouhou
,IOI 君の好きな文字列は Orinpikku
である.ここで,犬の名前を OJouhorinpikku
にすることを考える.これは以下のように 4 つの条件を満たす.
- 条件 1: 名前は英大文字と英小文字からなる.
- 条件 2: 文字列 S (
Jouhou
) は犬の名前OJouhorinpikku
の部分列である. - 条件 3: 文字列 T (
Orinpikku
) は犬の名前OJouhorinpikku
の部分列である. - 条件 4: K = 0 なので,この条件は満たしている.
また,これが 4 つの条件を満たす中で最も短い名前のひとつである.この文字数 14 を出力する.なお,英大文字と英小文字は区別されるため,jouhorinpikku
(文字数 13)などは条件を満たさない.
この入力例は小課題 4, 7, 8 の制約を満たす.
入力例 5
9 7 1 CoMMiTTee TeRRaCe
出力例 5
15
4 つの条件を満たす最も短い名前として CoMaMiTeRTeRaCe
などが考えられる.この文字数 15 を出力する.
この入力例は小課題 5, 6, 7, 8 の制約を満たす.
入力例 6
6 8 2 JOIIOI JOIGEGOI
出力例 6
9
4 つの条件を満たす最も短い名前は JOIGEIGOI
である.この文字数 9 を出力する.
この入力例は小課題 7, 8 の制約を満たす.