← 返回题目列表

AtCoder · joigsc2022_d

D. 复制并粘贴3

中文机器翻译题面 查看原题

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

コピー & ペースト 3 (Copy and Paste 3) - 原题 PDF 第 1 页
原题PDF第1页
コピー & ペースト 3 (Copy and Paste 3) - 原题 PDF 第 2 页
原题PDF第2页
コピー & ペースト 3 (Copy and Paste 3) - 原题 PDF 第 3 页
原题PDF第3页
コピー & ペースト 3 (Copy and Paste 3) - 原题 PDF 第 4 页
原始 PDF 第 4 部分
可复制的 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