codeforces-scrape

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

1260A.md (1968B)


      1 Source: https://codeforces.com/problemset/problem/1260/A
      2 
      3 A. Heating
      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 Several days ago you bought a new house and now you are planning to start a renovation. Since winters in your region can be very cold you need to decide how to heat rooms in your house.
     22 
     23 Your house has $n$ rooms. In the $i$-th room you can install at most $c_i$ heating radiators. Each radiator can have several sections, but the cost of the radiator with $k$ sections is equal to $k^2$ burles.
     24 
     25 Since rooms can have different sizes, you calculated that you need at least $sum_i$ sections in total in the $i$-th room.
     26 
     27 For each room calculate the minimum cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.
     28 
     29 Input
     30 
     31 The first line contains single integer $n$ ($1 \le n \le 1000$) — the number of rooms.
     32 
     33 Each of the next $n$ lines contains the description of some room. The $i$-th line contains two integers $c_i$ and $sum_i$ ($1 \le c_i, sum_i \le 10^4$) — the maximum number of radiators and the minimum total number of sections in the $i$-th room, respectively.
     34 
     35 Output
     36 
     37 For each room print one integer — the minimum possible cost to install at most $c_i$ radiators with total number of sections not less than $sum_i$.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 1 10000
     46 10000 1
     47 2 6
     48 4 6
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 100000000
     55 1
     56 18
     57 10
     58 ```
     59 
     60 Note
     61 
     62 In the first room, you can install only one radiator, so it's optimal to use the radiator with $sum_1$ sections. The cost of the radiator is equal to $(10^4)^2 = 10^8$.
     63 
     64 In the second room, you can install up to $10^4$ radiators, but since you need only one section in total, it's optimal to buy one radiator with one section.
     65 
     66 In the third room, there $7$ variants to install radiators: $[6, 0]$, $[5, 1]$, $[4, 2]$, $[3, 3]$, $[2, 4]$, $[1, 5]$, $[0, 6]$. The optimal variant is $[3, 3]$ and it costs $3^2+ 3^2 = 18$.