codeforces-scrape

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

1982B.md (2347B)


      1 Source: https://codeforces.com/problemset/problem/1982/B
      2 
      3 B. Collatz Conjecture
      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 Recently, the first-year student Maxim learned about the Collatz conjecture, but he didn't pay much attention during the lecture, so he believes that the following process is mentioned in the conjecture:
     22 
     23 There is a variable $x$ and a constant $y$. The following operation is performed $k$ times:
     24 
     25 * increase $x$ by $1$, then
     26 * while the number $x$ is divisible by $y$, divide it by $y$.
     27 
     28 Note that both of these actions are performed sequentially within one operation.
     29 
     30 For example, if the number $x = 16$, $y = 3$, and $k = 2$, then after one operation $x$ becomes $17$, and after another operation $x$ becomes $2$, because after adding one, $x = 18$ is divisible by $3$ twice.
     31 
     32 Given the initial values of $x$, $y$, and $k$, Maxim wants to know what is the final value of $x$.
     33 
     34 Input
     35 
     36 Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases. Then follows the description of the test cases.
     37 
     38 The only line of each test case contains three integers $x$, $y$, and $k$ ($1 \le x, k \le 10^{9}$, $2 \le y \le 10^{9}$) — the initial variable, constant and the number of operations.
     39 
     40 Output
     41 
     42 For each test case, output a single integer — the number obtained after applying $k$ operations.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 13
     50 
     51 1 3 1
     52 
     53 2 3 1
     54 
     55 24 5 5
     56 
     57 16 3 2
     58 
     59 2 2 1
     60 
     61 1337 18 1
     62 
     63 1 2 144133
     64 
     65 12345678 3 10
     66 
     67 998244353 2 998244353
     68 
     69 998244353 123456789 998244352
     70 
     71 998244354 998241111 998244352
     72 
     73 998244355 2 9982443
     74 
     75 1000000000 1000000000 1000000000
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 2
     82 1
     83 1
     84 2
     85 3
     86 1338
     87 1
     88 16936
     89 1
     90 21180097
     91 6486
     92 1
     93 2
     94 ```
     95 
     96 Note
     97 
     98 In the first test case, there is only one operation applied to $x = 1$, resulting in $x$ becoming $2$.
     99 
    100 In the second test case, for $x = 2$, within one operation, one is added to $x$ and it's divided by $y = 3$, resulting in $x$ becoming $1$.
    101 
    102 In the third test case, $x$ changes as follows:
    103 
    104 * After the first operation, $x = 1$, because $24 + 1 = 25$ and $25$ is divisible by $y = 5$ twice within one operation.
    105 * After the second operation, $x = 2$.
    106 * After the third operation, $x = 3$.
    107 * After the fourth operation, $x = 4$.
    108 * After the fifth operation, $x = 1$.