codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1418A.md (1686B)


      1 Source: https://codeforces.com/problemset/problem/1418/A
      2 
      3 A. Buying Torches
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are playing a very popular game called Cubecraft. Initially, you have one stick and want to craft $k$ torches. One torch can be crafted using one stick and one coal.
     22 
     23 Hopefully, you've met a very handsome wandering trader who has two trade offers:
     24 
     25 * exchange $1$ stick for $x$ sticks (you lose $1$ stick and gain $x$ sticks).
     26 * exchange $y$ sticks for $1$ coal (you lose $y$ sticks and gain $1$ coal).
     27 
     28 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.
     29 
     30 Your task is to find the minimum number of trades you need to craft at least $k$ torches. The answer always exists under the given constraints.
     31 
     32 You have to answer $t$ independent test cases.
     33 
     34 Input
     35 
     36 The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.
     37 
     38 The only line of the test case contains three integers $x$, $y$ and $k$ ($2 \le x \le 10^9$; $1 \le y, k \le 10^9$) — 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.
     39 
     40 Output
     41 
     42 For each test case, print the answer: the minimum number of trades you need to craft at least $k$ torches. The answer always exists under the given constraints.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 2 1 5
     51 42 13 24
     52 12 11 12
     53 1000000000 1000000000 1000000000
     54 2 1000000000 1000000000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 14
     61 33
     62 25
     63 2000000003
     64 1000000001999999999
     65 ```