分数: 500 点
问题陈述
某商店有卖 N 项目,编号为项目 1,项目 2, \ldots,项目 N.
项目 i (1\leq i\leq N) 的价格为 P_i 日元和价值 V_i。商店里的每种商品只有一份库存。
高桥选择一些商品,使得总价最多为 M 日元。
这里保证 M 至少是任何商品的价格。
也就是说,对于任意 1\leq i\leq N,存在一种选择项目的方法,使得总价最多为 M 日元和物品
包括 i 。
对于每个 1\leq i\leq N,确定以下三个类别项中的哪一个 i 属于:
- A 类:最大化所选商品的总价值(同时保持总价最多 M 日元),必须选择该项目。
- B 类:最大化所选商品的总价值(同时保持总价最多 M 日元),该项目可能会也可能不会被选择。
- C 类:最大化所选商品的总价值(同时保持总价最多 M 日元),绝不能选择该项目。
约束
- 1\leq N\leq 1000
- 1\leq M\leq 5\times 10^4
- 1\leq P_i\leq M
- 1\leq V_i\leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P_1 V_1 P_2 V_2 \vdots P_N V_N
输出
打印长度为的字符串 N 组成 A, B,和 C.
如果项目 i (1\leq i\leq N) 属于类别 X (其中 X 是 A、B 或 C), i输出字符串的第一个字符应该是 X.
示例输入 1
5 7 2 5 2 5 3 5 3 10 3 20
示例输出 1
BBCBA
选择商品时的最大可能总价值,使得总价最多为 7 日元是 30,可以通过以下方式之一实现:
- 选择项目 1, 2,和 5.
- 选择项目 4 和 5.
(没有其他方法可以选择总价最多为 7 日元,总价值为 30.)
因此,每个项目的类别如下:
- 项目 5 是必须选择的项目,以最大化所选项目(A 类)的总价值。
- 项目 1, 2,和 4 是可能会或可能不会被选择以最大化所选项目(B 类)总价值的项目。
- 项目 3 是决不能选择的项目,以最大化所选项目的总价值(C 类)。
因此,根据输出格式,打印 BBCBA.
示例输入 2
7 3 1 1 1 1 1 2 1 2 1 2 1 3 1 3
示例输出 2
CCBBBAA
选择任意一项时总价值最大化 3, 4, 5,以及项目 6 和 7.
请注意,即使商品具有相同的价格和价值,它们仍会被区分为不同的商品。