codeforces-scrape

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

1862D.md (2334B)


      1 Source: https://codeforces.com/problemset/problem/1862/D
      2 
      3 D. Ice Cream Balls
      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 Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.
     22 
     23 Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly $n$ different types of ice cream.
     24 
     25 There are plenty possible ice cream flavours: $1, 2, 3, \dots$. Tema can make two-balls ice cream with any flavours (probably the same).
     26 
     27 Two ice creams are considered different if their sets of ball flavours are different. For example, $\{1, 2\} = \{2, 1\}$, but $\{1, 1\} \neq \{1, 2\}$.
     28 
     29 For example, having the following ice cream balls: $\{1, 1, 2\}$, Tema can make only two types of ice cream: $\{1, 1\}$ and $\{1, 2\}$.
     30 
     31 Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone $\{x, x\}$ for some $x$, Tema needs at least $2$ balls of type $x$.
     32 
     33 Help Tema answer this question. It can be shown that answer always exist.
     34 
     35 Input
     36 
     37 Each test consists of multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of the test cases.
     38 
     39 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{18}$) — the number of ice cream types that Tema wants to make.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the minimum number of balls Tema needs to buy.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 1
     53 
     54 3
     55 
     56 6
     57 
     58 179
     59 
     60 1000000000000000000
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2
     67 3
     68 4
     69 27
     70 2648956421
     71 ```
     72 
     73 Note
     74 
     75 In the first sample, it is enough to have following balls types: $\{1, 1\}$. Note, that set $\{1\}$ if not enough since we need at least $2$ balls of a type $1$ in order to make such cone $\{1, 1\}$.
     76 
     77 In the second sample, it is not possible to make it with $2$ balls, but it can be done with these balls: $\{1, 2, 3\}$.
     78 
     79 In the third sample, $\{1, 2, 3, 4\}$ is optimal answer, so we can get following ice cream cones: $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$.