← 返回题目列表

Codeforces · 1260/A

A. 加热

中文机器翻译题面 查看原题

几天前,您买了一套新房子,现在正计划开始装修。由于您所在地区的冬天可能非常寒冷,您需要决定如何为家里的房间供暖。

你的房子有 $$$n$$$ 个房间。在第 $$$i$$$ 个房间中,您最多可以安装 $$$c_i$$$ 暖气片。每个散热器可以有多个部分,但具有 $$$k$$$ 部分的散热器的成本等于 $$$k^2$$$ burles。

由于房间可以有不同的大小,您计算出第 $$$i$$$ 个房间总共至少需要 $$$sum_i$$$ 个部分。

对于每个房间,计算安装最多 $$$c_i$$$ 个散热器的最低成本,且总节数不少于 $$$sum_i$$$。

输入

第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 房间数量。

接下来的 $$$n$$$ 行中的每一行都包含某个房间的描述。第 $$$i$$$ 行包含两个整数 $$$c_i$$$ 和 $$$sum_i$$$ ($$$1 \le c_i, sum_i \le 10^4$$$) — 分别是第 $$$i$$$ 房间中散热器的最大数量和分区的最小总数。

输出

对于每个房间,打印一个整数 — 安装最多 $$$c_i$$$ 散热器且总节数不少于 $$$sum_i$$$ 的最低可能成本。

示例

输入 #1

4
1 10000
10000 1
2 6
4 6

输出 #1

100000000
1
18
10

注意

在第一个房间中,您只能安装一个散热器,因此最好使用具有 $$$sum_1$$$ 部分的散热器。散热器的成本等于$$$(10^4)^2 = 10^8$$$。

在第二个房间,您最多可以安装 $$$10^4$$$ 散热器,但由于总共只需要一节,因此最好购买一台散热器。

在第三个房间,有 $$$7$$$ 种安装散热器:$$$[6, 0]$$$, $$$[5, 1]$$$, $$$[4, 2]$$$, $$$[3, 3]$$$, $$$[2, 4]$$$, $$$[1, 5]$$$, $$$[0, 6]$$$。最佳变体是 $$$[3, 3]$$$,成本为 $$$3^2+ 3^2 = 18$$$。