codeforces-scrape

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

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.