問題一覧 > 通常問題

No.1862 Copy and Paste

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : Chippppp / テスター : ぷら shiomusubi496
3 ProblemId : 7376 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-20 11:10:18

問題文

Chipppppくんは，文字 p を増やしたいと考えています．
今，文字列 S は p 一文字であり，文字列 T は空文字列です．

Chipppppくんは，以下の2つの操作をいくらでも行うことができます：

  • 操作 A：T を S で置き換える．A 秒かかる．
  • 操作 B：S の末尾に T を追加する．B 秒かかる．

S を N 文字以上にするためにかかる時間の最小値を求めてください．

入力

A B
N

  • 1≤A,B≤109
  • 1≤N≤109
  • 入力は全て整数

    • 出力

    S を N 文字以上にするためにかかる最小時間を出力してください．また，最後に改行を出力してください．

    サンプル

    サンプル1
    入力
    1 1
10
    出力
    7

    操作の一例を示します．

    • 操作 A を行う．S は p に，T は p になる．
    • 操作 B を行う．S は pp に，T は p になる．
    • 操作 A を行う．S は pp に，T は pp になる．
    • 操作 B を行う．S は pppp に，T は pp になる．
    • 操作 B を行う．S は pppppp に，T は pp になる．
    • 操作 A を行う．S は pppppp に，T は pppppp になる．
    • 操作 B を行う．S は pppppppppppp に，T は pppppp になる．

    操作 A を 3 回，操作 B を 4 回行っているので，1×3+1×4=7 より 7 秒かかります．6 秒以下で文字列 S を 10 文字以上にすることはできないため，7 を出力します．

    サンプル2
    入力
    1000 100
1
    出力
    0

    操作を行う必要がありません．

    サンプル3
    入力
    3 2
20
    出力
    20

    サンプル4
    入力
    33 4
74089
    出力
    334

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。