← 返回题目列表

AtCoder · awc0074_a

A. 剪彩

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

分数: 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