問題一覧 > 通常問題

No.1862 Copy and Paste

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 46
作問者 : Chippppp / テスター : ぷら shiomusubi496
お気に入りにしたユーザー ProblemId : 7376 / 自分の提出
問題文最終更新日: 2022-03-20 11:10:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 334 (順位表) の他の問題:

Problem Statement

Chipppppp wants to increase the number of characters p.
Currently, the string $S$ is the single character p, and the string $T$ is the empty string.

Chipppppp can perform the following two operations any number of times:

  • Operation A: Replace $T$ with $S$. This takes $A$ seconds.
  • Operation B: Append $T$ to the end of $S$. This takes $B$ seconds.

Find the minimum time required to make $S$ have at least $N$ characters.

Input

$A$ $B$
$N$

  • $1 \le A, B \le 10 ^ 9$
  • $1 \le N \le 10 ^ 9$
  • All inputs are integers.

    • Output

    Output the minimum time required to make $S$ have at least $N$ characters. Also, output a newline at the end.

    Sample

    Sample 1
    Input
    1 1
10
    Output
    7

    Here is one example of a sequence of operations.

    • Perform operation A. $S$ becomes p and $T$ becomes p.
    • Perform operation B. $S$ becomes pp and $T$ becomes p.
    • Perform operation A. $S$ becomes pp and $T$ becomes pp.
    • Perform operation B. $S$ becomes pppp and $T$ becomes pp.
    • Perform operation B. $S$ becomes pppppp and $T$ becomes pp.
    • Perform operation A. $S$ becomes pppppp and $T$ becomes pppppp.
    • Perform operation B. $S$ becomes pppppppppppp and $T$ becomes pppppp.

    Since operation A is performed $3$ times and operation B is performed $4$ times, this takes $1 \times 3 + 1 \times 4 = 7$ seconds, so $7$ seconds. It is impossible to make the string $S$ have at least $10$ characters in $6$ seconds or less, so output $7$.

    Sample 2
    Input
    1000 100
1
    Output
    0

    No operations need to be performed.

    Sample 3
    Input
    3 2
20
    Output
    20

    Sample 4
    Input
    33 4
74089
    Output
    334

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