問題一覧 > 通常問題

No.1862 Copy and Paste

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : ChipppppChippppp / テスター : ぷらぷら shiomusubi496shiomusubi496
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 \le A, B \le 10 ^ 9$
  • $1 \le N \le 10 ^ 9$
  • 入力は全て整数

    • 出力

    $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 \times 3 + 1 \times 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もしくは右上の雲マークをクリックしてアカウントを作成してください。