codeforces-scrape

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

2020B.md (2567B)


      1 Source: https://codeforces.com/problemset/problem/2020/B
      2 
      3 B. Brightness Begins
      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 Imagine you have $n$ light bulbs numbered $1, 2, \ldots, n$. Initially, all bulbs are on. To flip the state of a bulb means to turn it off if it used to be on, and to turn it on otherwise.
     22 
     23 Next, you do the following:
     24 
     25 * for each $i = 1, 2, \ldots, n$, flip the state of all bulbs $j$ such that $j$ is divisible by $i^\dagger$.
     26 
     27 After performing all operations, there will be several bulbs that are still on. Your goal is to make this number exactly $k$.
     28 
     29 Find the smallest suitable $n$ such that after performing the operations there will be exactly $k$ bulbs on. We can show that an answer always exists.
     30 
     31 $^\dagger$ An integer $x$ is divisible by $y$ if there exists an integer $z$ such that $x = y\cdot z$.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     36 
     37 The only line of each test case contains a single integer $k$ ($1 \le k \le 10^{18}$).
     38 
     39 Output
     40 
     41 For each test case, output $n$ — the minimum number of bulbs.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 1
     51 
     52 3
     53 
     54 8
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 5
     62 11
     63 ```
     64 
     65 Note
     66 
     67 In the first test case, the minimum number of bulbs is $2$. Let's denote the state of all bulbs with an array, where $1$ corresponds to a turned on bulb, and $0$ corresponds to a turned off bulb. Initially, the array is $[1, 1]$.
     68 
     69 * After performing the operation with $i = 1$, the array becomes $[\underline{0}, \underline{0}]$.
     70 * After performing the operation with $i = 2$, the array becomes $[0, \underline{1}]$.
     71 
     72 In the end, there are $k = 1$ bulbs on. We can also show that the answer cannot be less than $2$.
     73 
     74 In the second test case, the minimum number of bulbs is $5$. Initially, the array is $[1, 1, 1, 1, 1]$.
     75 
     76 * After performing the operation with $i = 1$, the array becomes $[\underline{0}, \underline{0}, \underline{0}, \underline{0}, \underline{0}]$.
     77 * After performing the operation with $i = 2$, the array becomes $[0, \underline{1}, 0, \underline{1}, 0]$.
     78 * After performing the operation with $i = 3$, the array becomes $[0, 1, \underline{1}, 1, 0]$.
     79 * After performing the operation with $i = 4$, the array becomes $[0, 1, 1, \underline{0}, 0]$.
     80 * After performing the operation with $i = 5$, the array becomes $[0, 1, 1, 0, \underline{1}]$.
     81 
     82 In the end, there are $k = 3$ bulbs on. We can also show that the answer cannot be smaller than $5$.