codeforces-scrape

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

269A.md (2089B)


      1 Source: https://codeforces.com/problemset/problem/269/A
      2 
      3 A. Magical Boxes
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Emuskald is a well-known illusionist. One of his trademark tricks involves a set of magical boxes. The essence of the trick is in packing the boxes inside other boxes.
     22 
     23 From the top view each magical box looks like a square with side length equal to 2*k* (*k* is an integer, *k* ≥ 0) units. A magical box *v* can be put inside a magical box *u*, if side length of *v* is strictly less than the side length of *u*. In particular, Emuskald can put 4 boxes of side length 2*k* - 1 into one box of side length 2*k*, or as in the following figure:
     24 
     25  ![](https://espresso.codeforces.com/3c55f85e515e2d768da08019ae7e04acc3a04023.png) 
     26 
     27 Emuskald is about to go on tour performing around the world, and needs to pack his magical boxes for the trip. He has decided that the best way to pack them would be inside another magical box, but magical boxes are quite expensive to make. Help him find the smallest magical box that can fit all his boxes.
     28 
     29 Input
     30 
     31 The first line of input contains an integer *n* (1 ≤ *n* ≤ 105), the number of different sizes of boxes Emuskald has. Each of following *n* lines contains two integers *k**i* and *a**i* (0 ≤ *k**i* ≤ 109, 1 ≤ *a**i* ≤ 109), which means that Emuskald has *a**i* boxes with side length 2*k**i*. It is guaranteed that all of *k**i* are distinct.
     32 
     33 Output
     34 
     35 Output a single integer *p*, such that the smallest magical box that can contain all of Emuskald’s boxes has side length 2*p*.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 2  
     43 0 3  
     44 1 5
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 3
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 1  
     57 0 4
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 1
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 2  
     70 1 10  
     71 2 2
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 3
     78 ```
     79 
     80 Note
     81 
     82 Picture explanation. If we have 3 boxes with side length 2 and 5 boxes with side length 1, then we can put all these boxes inside a box with side length 4, for example, as shown in the picture.
     83 
     84 In the second test case, we can put all four small boxes into a box with side length 2.