以下是来自日本的原始新闻PDF,已完整保存和染色。




可复制的 PDF 提取文本
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Copy and Paste 3
コピー& ペースト3 (Copy and Paste 3)
ただ奇妙な発明で知られるJOI 社は,最近Just Odd Editor というテキストエディタを開発した.
このテキストエディタでは,以下の操作のいずれかを繰り返すことで,文字列を入力することができる.
説明の都合上,現在テキストエディタの画面に表示されている文字列をX,クリップボードに保存されてい
る文字列をY とする.最初の時点では,X とY はどちらも空文字列である.
• 操作A:末尾に1 文字入力する.すなわち,ある文字c を決めて,X をX + c に更新する.
• 操作B:全選択して切り取りする.すなわち,Y をX に更新した後,X を空文字列に更新する.
• 操作C:末尾に貼り付けする.すなわち,X をX + Y に更新する.
ただし,文字または文字列x, y に対し,x + y は「x, y をこの順で連結した文字列」を表すものとする.また,
各操作には一定の時間がかかり,具体的には操作A, B, C を1 回行うのにそれぞれA, B,C 単位時間かかる.
あなたはJust Odd Editor をインストールしたので,できるだけ早く長さN の文字列S を入力したいと
思っている.すなわち,操作手順を工夫することで,できるだけ短い時間で画面に表示されている文字列を
S に一致させたい.
文字列の長さN,文字列S および各操作に必要な時間が与えられるので,文字列S を入力するのに必要
な時間の最小値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N
S
A
B
C
出力
標準出力に,文字列S を入力するのに必要な時間の最小値を1 行で出力せよ.
コピー& ペースト3– 1 / 4
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Copy and Paste 3
制約
• 1 ≦N ≦2 500.
• S は英小文字(’a’ - ’z’) からなる長さN の文字列である.
• 1 ≦A ≦1 000 000 000 (= 109).
• 1 ≦B ≦1 000 000 000 (= 109).
• 1 ≦C ≦1 000 000 000 (= 109).
• N, A, B,C は整数である.
小課題
1. (7 点) N = 3.
2. (18 点) S のすべての文字は’a’ である.
3. (18 点) N ≦30.
4. (11 点) N ≦200.
5. (22 点) N ≦1 000.
6. (24 点) 追加の制約はない.
入出力例
入力例1 出力例1
11 88
mississippi
10
5
2
以下の表のように操作すると,88 単位時間でmississippi を入力できる.これより少ない時間で
mississippi を入力することはできないので,88 を出力する.
順番 種類 操作内容 X Y 時間 累計時間
- - - "" "" - 0
1 操作A 末尾に1 文字入力 "s" "" 10 10
2 操作B 全選択して切り取り "" "s" 5 15
コピー& ペースト3– 2 / 4
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Copy and Paste 3
順番 種類 操作内容 X Y 時間 累計時間
3 操作C 末尾に貼り付け "s" "s" 2 17
4 操作C 末尾に貼り付け "ss" "s" 2 19
5 操作A 末尾に1 文字入力 "ssi" "s" 10 29
6 操作B 全選択して切り取り "" "ssi" 5 34
7 操作A 末尾に1 文字入力 "m" "ssi" 10 44
8 操作A 末尾に1 文字入力 "mi" "ssi" 10 54
9 操作C 末尾に貼り付け "missi" "ssi" 2 56
10 操作C 末尾に貼り付け "mississi" "ssi" 2 58
11 操作A 末尾に1 文字入力 "mississip" "ssi" 10 68
12 操作A 末尾に1 文字入力 "mississipp" "ssi" 10 78
13 操作A 末尾に1 文字入力 "mississippi" "ssi" 10 88
この入力例は小課題3, 4, 5, 6 の制約を満たす.
入力例2 出力例2
16 9
aaaaaaaaaaaaaaaa
1
1
1
以下の表のように操作すると,9 単位時間でaaaaaaaaaaaaaaaa を入力できる.これより少ない時間で
aaaaaaaaaaaaaaaa を入力することはできないので,9 を出力する.
順番 種類 操作内容 X Y 時間 累計時間
- - - "" "" - 0
1 操作A 末尾に1 文字入力 "a" "" 1 1
2 操作A 末尾に1 文字入力 "aa" "" 1 2
3 操作A 末尾に1 文字入力 "aaa" "" 1 3
4 操作A 末尾に1 文字入力 "aaaa" "" 1 4
5 操作B 全選択して切り取り "" "aaaa" 1 5
6 操作C 末尾に貼り付け "aaaa" "aaaa" 1 6
7 操作C 末尾に貼り付け "aaaaaaaa" "aaaa" 1 7
8 操作C 末尾に貼り付け "aaaaaaaaaaaa" "aaaa" 1 8
コピー& ペースト3– 3 / 4
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 1 – Copy and Paste 3
順番 種類 操作内容 X Y 時間 累計時間
9 操作C 末尾に貼り付け "aaaaaaaaaaaaaaaa" "aaaa" 1 9
この入力例は小課題2, 3, 4, 5, 6 の制約を満たす.
入力例3 出力例3
18 8060200000
aababbbababbbaabbb
1000000000
100000
10000000
この入力例は小課題3, 4, 5, 6 の制約を満たす.
コピー& ペースト3– 4 / 4