1929C.md (2806B)
1 Source: https://codeforces.com/problemset/problem/1929/C 2 3 C. Sasha and the Casino 4 5 time limit per test 6 7 2 seconds 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 Sasha decided to give his girlfriend the best handbag, but unfortunately for Sasha, it is very expensive. Therefore, Sasha wants to earn it. After looking at earning tips on the internet, he decided to go to the casino. 22 23 Sasha knows that the casino operates under the following rules. If Sasha places a bet of $y$ coins (where $y$ is a positive integer), then in case of winning, he will receive $y \cdot k$ coins (i.e., his number of coins will increase by $y \cdot (k - 1)$). And in case of losing, he will lose the entire bet amount (i.e., his number of coins will decrease by $y$). 24 25 Note that the bet amount must always be a positive ($ \gt 0$) integer and cannot exceed Sasha's current number of coins. 26 27 Sasha also knows that there is a promotion at the casino: he cannot lose more than $x$ times in a row. 28 29 Initially, Sasha has $a$ coins. He wonders whether he can place bets such that he is guaranteed to win any number of coins. In other words, is it true that for any integer $n$, Sasha can make bets so that for any outcome that does not contradict the rules described above, at some moment of time he will have at least $n$ coins. 30 31 Input 32 33 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of the test cases follows. 34 35 The single line of each test case contains three integers $k, x$ and $a$ ($2 \leq k \leq 30$, $1 \leq x \leq 100$, $1 \leq a \leq 10^9$) — the number of times the bet is increased in case of a win, the maximum number of consecutive losses, and the initial number of coins Sasha has. 36 37 Output 38 39 For each test case, output "YES" (without quotes) if Sasha can achieve it and "NO" (without quotes) otherwise. 40 41 You can output "YES" and "NO" in any case (for example, the strings "yEs", "yes" and "Yes" will be recognized as a positive answer). 42 43 Example 44 45 Input 46 47 ``` 48 9 49 50 2 1 7 51 52 2 1 1 53 54 2 3 15 55 56 3 3 6 57 58 4 4 5 59 60 5 4 7 61 62 4 88 1000000000 63 64 25 69 231 65 66 13 97 18806 67 ``` 68 69 Output 70 71 ``` 72 YES 73 NO 74 YES 75 NO 76 NO 77 YES 78 NO 79 NO 80 NO 81 ``` 82 83 Note 84 85 In the first test case, Sasha can proceed as follows: 86 87 * If Sasha places a bet for the first time or if he won the previous bet, then he places $1$ coin. 88 * If Sasha lost the previous bet, then he places $2$ coins. 89 90 Note that Sasha cannot lose more than once in a row. 91 92 It can be proven that with this strategy, Sasha can obtain as many coins as he wants. 93 94 In the second test case, Sasha can only place $1$ coin for the first time. But in case of a loss, he will not be able to place any more bets, so he will not be able to guarantee having as many coins as he wants.