← 返回题目列表

Codeforces · 1386/B

B. 混合物

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

著名餐厅“Salt, Pepper & Garlic”的主厨 Serge 正在努力获得他的第一颗米其林星。他被告知一位秘密专家计划今晚访问他的餐厅。

尽管专家的名字尚未透露,但 Serge 确信他知道会点菜单中的哪道菜以及专家的口味偏好。也就是说,专家要求他的菜肴中盐、胡椒粉和蒜粉的比例极其精确。

Serge 在厨房的一个特殊架子上放了一套装有盐、胡椒粉和大蒜粉混合物的瓶子。对于每一瓶,他都知道每种成分的确切数量(以千克为单位)。 Serge 可以组合任意数量的瓶装混合物(或直接使用其中之一),以获得特定菜肴所需的特定比例的混合物。

幸运的是,需要添加到菜肴中的混合物的绝对量非常小,因此您可以假设瓶子中的量始终是足够的。然而,描述比例的数值可能相当大。

Serge 想知道是否有可能从可用的瓶子中获得专家最喜欢的混合物,如果可以的话,实现这一目标所需的最少瓶子数量是多少。

此外,随着 Serge 收到新瓶子或将其借给其他厨师,架子上的瓶子组可能会随着时间而变化。所以他想在每次这样的改变之后回答这个问题。

例如,假设专家最喜欢的混合物是 $$$1:1:1$$$ 并且货架上有三瓶混合物:

$$$$$$ \begin{array}{cccc} \hline \text{混合物} & \text{盐} & \text{胡椒} & \text{蒜粉} \\ \hline 1 & 10 & 20 & 30 \\ 2 & 300 & 200 & 100 \\ 3 & 12 & 15 & 27 \\ 3 & 12 & 15 & 27 \hline \end{array} $$$$$$ 瓶子中的成分量,千克

为了获得所需的混合物,使用瓶子 1 和 2 中等量的混合物就足够了。如果瓶子 2 被移除,则不再可能获得它。

编写一个程序来帮助 Serge 解决这个任务!

输入

第一行包含三个非负整数 $$$S_f$$$、$$$P_f$$$ 和 $$$G_f$$$ ($$$0 \leq S_f, P_f, G_f$$$; $$$0 < S_f+P_f+G_f \leq 10^6$$$) 描述专家最喜欢的盐、胡椒和大蒜粉的量混合物。对于任何真实的 $$$\alpha>0$$$,$$$(\alpha{S_f}, \alpha{P_f}, \alpha{G_f})$$$ 也是专家最喜欢的混合物。

第二行有一个正整数$$$N$$$(货架上的更改数量,$$$N \leq 100\,000$$$)。您应该假设最初架子是空的。

接下来的 $$$N$$$ 行描述了书架上的单个更改:

- 如果添加新瓶子,则该行包含大写字母 $$$A$$$ 后跟三个非负整数 $$$S_i$$$、$$$P_i$$$ 和 $$$G_i$$$ ($$$0 \leq S_i, P_i, G_i$$$; $$$0 < S_i+P_i+G_i \leq 10^6$$$) 描述添加的瓶子中盐、胡椒粉和大蒜粉的量。添加的瓶子由从$$$1$$$开始的唯一整数连续编号,即第$$$i$$$个瓶子对应于输入数据中第$$$i$$$个添加的瓶子。
- 如果从货架上移除特定瓶子,则该行包含大写字母 $$$R$$$ 后跟整数 - 瓶子编号 $$$r_i$$$。清除中的所有值 $$$r_i$$$ 都是唯一的,$$$r_i$$$ 从未超过迄今为止添加的瓶子总数。

输出

输出 $$$N$$$ 行。第 $$$j$$$ 行 ($$$1 \leq j \leq N$$$) 应包含数字 $$$x_j$$$,即使用货架上第一次 $$$j$$$ 更改后可用的瓶子制备具有专家最喜欢的盐、胡椒和大蒜粉比例的混合物所需的最小瓶子数量,或者如果不可能,则为 $$$0$$$。

示例

输入 #1

1 2 3
6
A 5 6 7
A 3 10 17
R 1
A 15 18 21
A 5 10 15
R 3

输出 #1

0
2
0
2
1
1

注意

评分:
子任务:

1. (13 分) $$$N \leq 50$$$, $$$0 < S_i+P_i+G_i \leq 10^2$$$
2. (17 分) $$$N \leq 500$$$, $$$0 < S_i+P_i+G_i \leq 10^3$$$
3. (30 分) $$$N \leq 5000$$$, $$$0 < S_i+P_i+G_i \leq 10^4$$$
4.(40分)没有进一步的限制

请注意,在示例中,$$$1$$$ 和 $$$3$$$ 瓶子中含有相同比例的盐、胡椒粉和大蒜粉。