#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 5
14

提示

数据约定:
对于100%的数据:
2 <= x <= 109
1 <= y, k <= 109