問題一覧 > 通常問題

No.915 Plus Or Multiple Operation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 143
作問者 : ningenMeningenMe / テスター : tpynerivertpyneriver
10 ProblemId : 3389 / 出題時の順位表
問題文最終更新日: 2019-10-26 00:21:27

問題文

くる君は最初$0$枚のクッキーを持っています。くる君はクッキーを$A$枚ちょうどにしたいです。
クッキーを増やすには次の$2$種類の操作があります。

 ・$B$円を支払う。$1$以上$C$未満の数字$i$を一つ選び、クッキーを購入する。クッキーの枚数が$i$増える。
 ・$B$円を支払う。クッキーを叩き割る許可を得ることができ、クッキーの枚数が$C$倍になる。

上記の操作は好きな順番で好きな回数行うことができます。
くる君は出来るだけ少ないお金でクッキーを$A$枚ちょうどにしたいです。その最小コストを求めてください。
クッキーを$A$枚ちょうどにできないときは$-1$を出力してください。

なお入力は$Q$クエリ与えられるので、それぞれに対して答えを求めてください。

入力

$Q$
$A_1\ B_1\ C_1$
$\vdots$
$A_Q\ B_Q\ C_Q$

入力は全て整数である
$1 \le Q \le 20$
$1 \le A_i,B_i,C_i \le 10^9\ (1 \le i \le Q)$

出力

$Q$行出力してください。
$A_i,B_i,C_i$をそれぞれ問題文中の$A,B,C$としてクエリに答えてください。
1クエリごとに改行してください。

サンプル

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

下記のように遷移することで$1×3=3$円で$7$枚にすることができます。
$\ 0$ (初期状態)
→ $(+2)\ 2\ $
→ $(×3)\ 6\ $
→ $(+1)\ 7\ $

サンプル2
入力
1
133 2 5
出力
12

下記のように遷移することで$2×6=12$円で$133$枚にすることができます。
$\ 0$ (初期状態)
→ $(+1)\ 1\ $
→ $(×5)\ 5\ $
→ $(×5)\ 25\ $
→ $(×5)\ 125\ $
→ $(+4)\ 129\ $
→ $(+4)\ 133\ $

サンプル3
入力
2
12345789 987654321 57
12 2 3
出力
7901234568
6

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