分数: 625 点
问题陈述
有 10^{100} 孩子们在比赛场地。最初,没有孩子获得任何奖牌。
孩子恰好在他们离开场地时 退出 or 逃脱.
游戏包括 N 天。当天 i (1 \leq i \leq N),按顺序执行以下操作序列。
- 收集现场孩子们所持有的所有奖牌,让 s 是收集的奖牌总数。
- 分发 s + A_i 奖牌在场内的孩子们之间自由发放(如果场馆里没有孩子,则不执行任何操作)。
- 在会场的孩子中,那些少于 B_i 奖牌掉落。那些至少有 B_i 奖牌各丢失 B_i 奖牌。
- 在会场的孩子中,至少有 C_i 奖牌各自选择此时是否逃跑或留在场地。
比赛结束时留在场地的孩子 N 天辍学。
找出最终逃脱的孩子的最大可能数量。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 3 \times 10^5
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^6
- 1 \leq B_i \leq 10^6
- 1 \leq C_i \leq 10^6
- 总和 N 所有测试用例最多 3 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}
每个测试用例均按以下格式给出:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
2 4 16 2 3 15 2 4 1 3 5 20 5 5 2 41404 1 941738 211877 205711 417821
示例输出 1
5 0
考虑第一个测试用例。通过执行以下操作,五个孩子就可以逃脱。
- 在一天开始时 1, 收集 s = 0 奖牌来自 10^{100} 孩子们。然后,按以下步骤操作。
- 分发 0 + 16 = 16 奖牌,让孩子们的奖牌数量变得 (5, 5, 2, 2, 2, 0, \dots, 0).
- 的 10^{100} - 5 没有奖牌的孩子被淘汰,剩下的 5 孩子们的奖牌数变为 (3, 3, 0, 0, 0).
- 的 2 孩子们 3 奖章各选择逃跑,剩余的 3 孩子们的奖牌数变为 (0, 0, 0).
- 在一天开始时 2, 收集 s = 0 奖牌来自 3 孩子们。然后,按以下步骤操作。
- 分发 0 + 15 = 15 奖牌,这样孩子们的奖牌计数就变成了 (6, 6, 3).
- 没有人退出,剩下的 3 孩子们的奖牌数变为 (4, 4, 1).
- 1 孩子与 4 勋章选择逃跑,剩下的 2 孩子们的奖牌数变为 (4, 1).
- 在一天开始时 3, 收集 s = 5 奖牌来自 2 孩子们。然后,按以下步骤操作。
- 分发 5 + 1 = 6 奖牌,这样孩子们的奖牌计数就变成了 (3, 3).
- 没有人退出,剩下的 2 孩子们的奖牌数变为 (0, 0).
- 无人逃脱。
- 在一天开始时 4, 收集 s = 0 奖牌来自 2 孩子们。然后,按以下步骤操作。
- 分发 0 + 20 = 20 奖牌,这样孩子们的奖牌计数就变成了 (10, 10).
- 没有人退出,剩下的 2 孩子们的奖牌数变为 (5, 5).
- 的 2 孩子们 5 奖牌各自选择逃跑,场地变得空荡荡。
在第二个测试用例中,没有一个孩子能够逃脱。