codeforces-scrape

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

1099B.md (2527B)


      1 Source: https://codeforces.com/problemset/problem/1099/B
      2 
      3 B. Squares and Segments
      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 Little Sofia is in fourth grade. Today in the geometry lesson she learned about segments and squares. On the way home, she decided to draw $n$ squares in the snow with a side length of $1$. For simplicity, we assume that Sofia lives on a plane and can draw only segments of length $1$, parallel to the coordinate axes, with vertices at integer points.
     22 
     23 In order to draw a segment, Sofia proceeds as follows. If she wants to draw a vertical segment with the coordinates of the ends $(x, y)$ and $(x, y+1)$. Then Sofia looks if there is already a drawn segment with the coordinates of the ends $(x', y)$ and $(x', y+1)$ for some $x'$. If such a segment exists, then Sofia quickly draws a new segment, using the old one as a guideline. If there is no such segment, then Sofia has to take a ruler and measure a new segment for a long time. Same thing happens when Sofia wants to draw a horizontal segment, but only now she checks for the existence of a segment with the same coordinates $x$, $x+1$ and the differing coordinate $y$.
     24 
     25 For example, if Sofia needs to draw one square, she will have to draw two segments using a ruler:
     26 
     27  ![](https://espresso.codeforces.com/1106062ecf107756442b2078cc39ce0c8ea9852e.png) 
     28 
     29 After that, she can draw the remaining two segments, using the first two as a guide:
     30 
     31  ![](https://espresso.codeforces.com/bff105c8889fd0d8858fa3847d2f55ef998d6838.png) 
     32 
     33 If Sofia needs to draw two squares, she will have to draw three segments using a ruler:
     34 
     35  ![](https://espresso.codeforces.com/09265ebf94202777571edcc0aa9e40381706b95a.png) 
     36 
     37 After that, she can draw the remaining four segments, using the first three as a guide:
     38 
     39  ![](https://espresso.codeforces.com/c94cf5449099f4a66d2f8ed847911a7a55f93ba0.png) 
     40 
     41 Sofia is in a hurry, so she wants to minimize the number of segments that she will have to draw with a ruler without a guide. Help her find this minimum number.
     42 
     43 Input
     44 
     45 The only line of input contains a single integer $n$ ($1 \le n \le 10^{9}$), the number of squares that Sofia wants to draw.
     46 
     47 Output
     48 
     49 Print single integer, the minimum number of segments that Sofia will have to draw with a ruler without a guide in order to draw $n$ squares in the manner described above.
     50 
     51 Examples
     52 
     53 Input
     54 
     55 ```
     56 1
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 2
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 2
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 3
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 4
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 4
     87 ```