#J3052. 合成火炬
合成火炬
题目描述
小紫在玩一款叫做Torchcraft的游戏。在Torchcraft中,每当你开始新游戏时,你初始都会得到一根木棍,而通关条件就是合成至少k个火炬。火炬的合成公式如下:木棍*1+煤*1=火炬*1。
小紫在游玩过程中碰到了一个商人,根据屏幕上的按键提示,小紫按下了E键与商人进行了交互。此时她的屏幕上弹出了一个对话框,对话框的内容如下所示:
|
交易物品 |
||
| 需求物品 | 得到物品 | 操作 |
| 木棍*1 |
木棍*x |
交易 |
| 木棍*y | 煤*1 | 交易 |
经过不断的交易,小紫终于合成出了k个火炬,游戏于是也通关了。
现在,小紫想拜托聪明的你设计一个算法,来找出达成游戏通关目标的最少交易次数。
输入格式
输入共1行。第1行有三个正整数x, y, k,其中x表示用一根木棍可以换得的木棍数,y表示换一块煤需要的木棍数,k表示游戏通关需要的最少火炬数。数字之间使用空格隔开。
输出格式
输出1行,即合成出至少k个火炬的最少交易次数。2 1 514
提示
数据约定:对于100%的数据:
2 <= x <= 109
1 <= y, k <= 109