G. 孩子们渴望邪恶的幼儿园

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

孩子们渴望邪恶的幼儿园

Children Yearn for the Evil Kindergarten

AtCoder

⌀ 2831

原题

← F→

孩子们渴望邪恶的幼儿园AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There are $10^{100}$ kids at a game venue. Initially, no kid has any medals.

游戏场地有 $10^{100}$ 个孩子。最初，每个孩子都没有奖牌。AI (CI翻译)

A kid leaves the venue exactly when they either drop out or escape.

孩子会在退场或逃跑时离开场地。AI (CI翻译)

The game consists of $N$ days. On day $i$ ( $1 \leq i \leq N$ ), the following sequence of operations is performed in order.

游戏共进行 $N$ 天。在第 $i$ 天（ $1 \leq i \leq N$ ），按顺序进行以下操作。AI (CI翻译)

Collect all medals held by the kids at the venue, and let $s$ be the total number of collected medals.
Distribute $s + A_i$ medals freely among the kids at the venue (if there are no kids at the venue, do nothing).
Among the kids at the venue, those with fewer than $B_i$ medals drop out. Those with at least $B_i$ medals each lose $B_i$ medals.
Among the kids at the venue, those with at least $C_i$ medals each choose whether to escape at this point or remain at the venue.

收集场地内所有孩子持有的奖牌，设收集到的奖牌总数为 $s$ 。
将 $s + A_i$ 枚奖牌任意分配给场地内的孩子（如果场地内没有孩子，则什么也不做）。
场地内奖牌数少于 $B_i$ 的孩子退场。奖牌数至少为 $B_i$ 的孩子每人失去 $B_i$ 枚奖牌。
场地内奖牌数至少为 $C_i$ 的孩子各自选择此时逃跑或留在场地内。

AI (CI翻译)

Kids who remain at the venue at the end of the $N$ days drop out.

在 $N$ 天结束时仍留在场地内的孩子会退场。AI (CI翻译)

Find the maximum possible number of kids who ultimately escape.

求最终能够逃跑的孩子数的最大值。AI (CI翻译)

You are given $T$ test cases; solve each of them.

给定 $T$ 个测试用例，请分别求出每个测试用例的答案。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$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$
The sum of $N$ over all test cases is at most $3 \times 10^5$ .
All input values are integers.

$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$ 。
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入给出，格式如下：AI (CI翻译)

T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}

T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}

AI (CI翻译)

Each test case is given in the following format:

每个测试用例的格式如下：AI (CI翻译)

N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answers for the test cases in order, separated by newlines.

按顺序输出每个测试用例的答案，每个答案占一行。AI (CI翻译)

样例

Input #1

2
4
16 2 3
15 2 4
1 3 5
20 5 5
2
41404 1 941738
211877 205711 417821

Output #1

5
0

Consider the first test case. By acting as follows, five kids can escape. - At the start of day $1$, collect $s = 0$ medals from $10^{100}$ kids. Then, proceed as follows. - Distribute $0 + 16 = 16$ medals so that the kids' medal counts become $(5, 5, 2, 2, 2, 0, \dots, 0)$. - The $10^{100} - 5$ kids with no medals drop out, and the remaining $5$ kids' medal counts become $(3, 3, 0, 0, 0)$. - The $2$ kids with $3$ medals each choose to escape, and the remaining $3$ kids' medal counts become $(0, 0, 0)$. - At the start of day $2$, collect $s = 0$ medals from $3$ kids. Then, proceed as follows. - Distribute $0 + 15 = 15$ medals so that the kids' medal counts becomes $(6, 6, 3)$. - No one drops out, and the remaining $3$ kids' medal counts become $(4, 4, 1)$. - $1$ kid with $4$ medals chooses to escape, and the remaining $2$ kids' medal counts become $(4, 1)$. - At the start of day $3$, collect $s = 5$ medals from $2$ kids. Then, proceed as follows. - Distribute $5 + 1 = 6$ medals so that the kids' medal counts becomes $(3, 3)$. - No one drops out, and the remaining $2$ kids' medal counts become $(0, 0)$. - No one escapes. - At the start of day $4$, collect $s = 0$ medals from $2$ kids. Then, proceed as follows. - Distribute $0 + 20 = 20$ medals so that the kids' medal counts becomes $(10, 10)$. - No one drops out, and the remaining $2$ kids' medal counts become $(5, 5)$. - The $2$ kids with $5$ medals each choose to escape, and the venue becomes empty. In the second test case, not a single kid can escape.

题目信息

题号

abc458_g

所属比赛

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。