codeforces-scrape

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

760B.md (1702B)


      1 Source: https://codeforces.com/problemset/problem/760/B
      2 
      3 B. Frodo and pillows
      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 *n* hobbits are planning to spend the night at Frodo's house. Frodo has *n* beds standing in a row and *m* pillows (*n* ≤ *m*). Each hobbit needs a bed and at least one pillow to sleep, however, everyone wants as many pillows as possible. Of course, it's not always possible to share pillows equally, but any hobbit gets hurt if he has at least two pillows less than some of his neighbors have.
     22 
     23 Frodo will sleep on the *k*-th bed in the row. What is the maximum number of pillows he can have so that every hobbit has at least one pillow, every pillow is given to some hobbit and no one is hurt?
     24 
     25 Input
     26 
     27 The only line contain three integers *n*, *m* and *k* (1 ≤ *n* ≤ *m* ≤ 109, 1 ≤ *k* ≤ *n*) — the number of hobbits, the number of pillows and the number of Frodo's bed.
     28 
     29 Output
     30 
     31 Print single integer — the maximum number of pillows Frodo can have so that no one is hurt.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 4 6 2
     39 ```
     40 
     41 Output
     42 
     43 ```
     44 2
     45 ```
     46 
     47 Input
     48 
     49 ```
     50 3 10 3
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 4
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 3 6 1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 3
     69 ```
     70 
     71 Note
     72 
     73 In the first example Frodo can have at most two pillows. In this case, he can give two pillows to the hobbit on the first bed, and one pillow to each of the hobbits on the third and the fourth beds.
     74 
     75 In the second example Frodo can take at most four pillows, giving three pillows to each of the others.
     76 
     77 In the third example Frodo can take three pillows, giving two pillows to the hobbit in the middle and one pillow to the hobbit on the third bed.