31640번 - 名前 (Name) 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 56 | 13 | 13 | 43.333% |
문제
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 が与えられたとき，犬に付ける名前の文字数を求めるプログラムを作成せよ．
입력
入力は以下の形式で与えられる．
N M K S T
출력
犬に付ける名前の文字数を 1 行で出力せよ．
제한
- 1 ≦ N ≦ 500．
- 1 ≦ M ≦ 500．
- 0 ≦ K ≦ 3．
- S は英大文字と英小文字からなる長さ N の文字列である．
- T は英大文字と英小文字からなる長さ M の文字列である．
- N, M, K は整数である．
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | S = T，K = 0． |
| 2 | 7 | S = T，K = 1． |
| 3 | 16 | S = T． |
| 4 | 17 | K = 0． |
| 5 | 13 | K = 1，N ≦ 25，M ≦ 25． |
| 6 | 15 | K = 1． |
| 7 | 20 | K ≦ 2． |
| 8 | 10 | 追加の制約はない． |
예제 입력 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 の制約を満たす．
출처
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2023/2024 5번
채점 및 기타 정보
- 예제는 채점하지 않는다.