← 返回题目列表

AtCoder · abc458_g

G. 孩子们向往邪恶的幼儿园

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

分数: 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 奖牌各自选择逃跑,场地变得空荡荡。

在第二个测试用例中,没有一个孩子能够逃脱。