codeforces-scrape

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

913C.md (1927B)


      1 Source: https://codeforces.com/problemset/problem/913/C
      2 
      3 C. Party Lemonade
      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 A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.
     22 
     23 Your favorite store sells lemonade in bottles of *n* different volumes at different costs. A single bottle of type *i* has volume 2*i* - 1 liters and costs *c**i* roubles. The number of bottles of each type in the store can be considered infinite.
     24 
     25 You want to buy at least *L* liters of lemonade. How many roubles do you have to spend?
     26 
     27 Input
     28 
     29 The first line contains two integers *n* and *L* (1 ≤ *n* ≤ 30; 1 ≤ *L* ≤ 109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.
     30 
     31 The second line contains *n* integers *c*1, *c*2, ..., *c**n* (1 ≤ *c**i* ≤ 109) — the costs of bottles of different types.
     32 
     33 Output
     34 
     35 Output a single integer — the smallest number of roubles you have to pay in order to buy at least *L* liters of lemonade.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4 12  
     43 20 30 70 90
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 150
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4 3  
     56 10000 1000 100 10
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 10
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 4 3  
     69 10 100 1000 10000
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 30
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 5 787787787  
     82 123456789 234567890 345678901 456789012 987654321
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 44981600785557577
     89 ```
     90 
     91 Note
     92 
     93 In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.
     94 
     95 In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.
     96 
     97 In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.