分数: 233 分
问题陈述
高桥是手工艺俱乐部的主席。作为文化节的准备,他需要削减 N 将丝带切成指定长度以制作装饰部件。
的 i第 丝带的长度为 L_i 毫米,每个零件的指定长度为 T_i 毫米。对于每条丝带,部分 T_i 从一端开始依次切出毫米。通过这种方式获得的零件数量为 \lfloor L_i / T_i \rfloor,则切割后剩余废料的长度为 R_i = L_i \bmod T_i 毫米。
顾问青木老师制定了以下规则:“如果还有剩余的废品(R_i > 0)且其长度至少为指定长度的一半,即 R_i \geq \lfloor T_i / 2 \rfloor,那么该废料也可以用作一个零件。”
综上所述,零件数量 P_i 从 i第色带确定如下:
P_i = \begin{cases} \lfloor L_i / T_i \rfloor + 1 & \text{(if } R_i > 0 \text{ and } R_i \geq \lfloor T_i / 2 \rfloor \text{)} \\ \lfloor L_i / T_i \rfloor & \text{(otherwise)} \end{cases}
这里,“否则”是指没有剩余废料的情况(R_i = 0),或者存在废料但其长度小于的情况 \lfloor T_i / 2 \rfloor (0 < R_i < \lfloor T_i / 2 \rfloor).
请注意,即使在以下情况下,此规则也以相同的方式适用: L_i < T_i。在这种情况下, \lfloor L_i / T_i \rfloor = 0,整个丝带变成了一段长度的碎片 R_i = L_i。如果废料长度至少为 \lfloor T_i / 2 \rfloor,则得到一份;否则,获得零份。
对于每个 N 丝带,确定获得的零件数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq 10^{18}
- 1 \leq T_i \leq 10^{18}
- 所有输入值均为整数。
输入
N L_1 T_1 L_2 T_2 \vdots L_N T_N
第一行包含一个整数 N 代表色带数量。以下每一项 N 行,其中 i- 第行 (1 \leq i \leq N),包含长度 L_i 的 i第一个色带和指定的部分长度 T_i,用空格分隔。
输出
输出 N 行。的 i- 第行 (1 \leq i \leq N)应包含从 i- 第一个功能区。
示例输入 1
5 10 3 10 5 7 4 7 5 7 6
示例输出 1
4 2 2 2 1
示例输入 2
5 5 3 4 3 3 7 2 7 100 100
示例输出 2
2 2 1 0 1
示例输入 3
8 1000 300 1000 400 999 500 123456 789 50 99 50 100 50 101 1 1
示例输出 3
3 3 2 156 1 1 1 1
示例输入 4
10 1000000000000000000 1 1000000000000000000 3 999999999999999999 2 1000000000000000000 1000000000000000000 999999999999999999 1000000000000000000 500000000000000000 1000000000000000000 499999999999999999 1000000000000000000 7 2 123456789012345678 987654321 1000000000000000000 7
示例输出 4
1000000000000000000 333333333333333334 500000000000000000 1 1 1 0 4 124999999 142857142857142857
示例输入 5
6 1 1 1 2 1 3 1 1000000000000000000 1000000000000000000 1000000000000000000 2 1
示例输出 5
1 1 1 0 1 2