codeforces-scrape

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

2169D1.md (1847B)


      1 Source: https://codeforces.com/problemset/problem/2169/D1
      2 
      3 D1. Removal of a Sequence (Easy Version)
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is the easy version of the problem. The difference between the versions is the constraint on $x$; in this version, $x \le 10^5$.
     22 
     23 Polycarp has a sequence of all natural numbers from $1$ to $10^{12}$. He decides to modify this sequence by performing the following action $x$ times:
     24 
     25 * Simultaneously remove all numbers at positions $y$, $2 \cdot y$, $3 \cdot y$, ..., $m \cdot y \le n$, where $n$ is the length of the current sequence.
     26 
     27 After that, Polycarp wants to find the $k$-th number in the remaining sequence or determine that the length of the resulting sequence is less than $k$.
     28 
     29 Help Polycarp solve this problem!
     30 
     31 Consider an example. Let $x = 2$, $y = 3$, $k = 5$, then:
     32 
     33  ![](https://espresso.codeforces.com/d72e39099c3d7824b722e3747c0a15a60a44a6c9.png) 
     34 
     35 The numbers crossed out with a red line were removed after the first operation, and the numbers crossed out with a blue line were removed after the second operation. Thus, the number at position $k = 5$ is the number $10$.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10$). The description of the test cases follows.
     40 
     41 The only line of each test case contains three integers $x$, $y$, $k$ ($1 \le x \le \bf{10^{5}}$, $1 \le y, k \le 10^{12}$).
     42 
     43 Output
     44 
     45 For each test case, output a positive integer that is at the $k$-th position in the resulting sequence, or $-1$ if the length of the resulting sequence is less than $k$.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 2 3 5
     55 
     56 2 5 1
     57 
     58 20 2 1000000000000
     59 
     60 175 10 28
     61 
     62 100000 998244353 1999999999
     63 
     64 1 1 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 10
     71 
     72 1
     73 
     74 -1
     75 
     76 2339030304
     77 
     78 2000199999
     79 
     80 -1
     81 ```