time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are playing a very popular game called Cubecraft. Initially, you have one stick and want to craft kk torches. One torch can be crafted using one stick and one coal.
Hopefully, you've met a very handsome wandering trader who has two trade offers:
- exchange 11 stick for xx sticks (you lose 11 stick and gain xx sticks).
- exchange yy sticks for 11 coal (you lose yy sticks and gain 11 coal).
During one trade, you can use only one of these two trade offers. You can use each trade offer any number of times you want to, in any order.
Your task is to find the minimum number of trades you need to craft at least kk torches. The answer always exists under the given constraints.
You have to answer tt independent test cases.
Input
The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases. Then tt test cases follow.
The only line of the test case contains three integers xx, yy and kk (2≤x≤1092≤x≤109; 1≤y,k≤1091≤y,k≤109) — the number of sticks you can buy with one stick, the number of sticks required to buy one coal and the number of torches you need, respectively.
Output
For each test case, print the answer: the minimum number of trades you need to craft at least kk torches. The answer always exists under the given constraints.
Example
input
Copy
5 2 1 5 42 13 24 12 11 12 1000000000 1000000000 1000000000 2 1000000000 1000000000
output
Copy
14 33 25 2000000003 1000000001999999999
解题说明:此题是一道模拟题,采用贪心方法求解,容易发现最少需要k ∗ y 根木棒,进行的最少交易次数为k,只需要判断要进行多少次交易才能超过需要的木棒根数:k ∗ y + k根即可。
#include<stdio.h>
int main()
{
int n, i;
long long x, y, k, s1;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%lld %lld %lld", &x, &y, &k);
s1 = (k*y + k - 1) / (x - 1);
if ((k*y + k - 1) % (x - 1) != 0)
{
s1++;
}
printf("%lld\n", s1 + k);
}
return 0;
}