分数: 350 点
问题陈述
你有两种类型的糖果无限供应:小糖果和大糖果。 一颗小糖果的重量是 X 克,一块大糖果的重量是 Y 克。大糖果比小糖果重(也就是说, X < Y).
有 N 儿童,已编号 1 to N.
您决定分发糖果,以满足以下条件:
- 对于 i=1,\dots,N,孩子 i 准确接收 A_i 糖果共有两种类型。
- 分配给的糖果总重量 N 孩子们都是平等的。
判断是否存在满足条件的分发方式。如果存在,请找出分发的大糖果数量的最大可能值。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X < Y \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X Y A_1 \dots A_N
输出
如果没有满足条件的分配方法,则输出 -1.
如果存在满足条件的分配方法,则输出该分配方法中分配的大糖果数量的最大可能值。
示例输入 1
3 6 8 11 10 13
示例输出 1
18
您可以按如下方式分发糖果,以便分发给孩子们的糖果总重量都相等。
- 儿童 1 收到 4 小糖果和 7 大糖果。总重量为 6 \times 4 + 8 \times 7 = 80 克。
- 儿童 2 收到 0 小糖果和 10 大糖果。总重量为 6 \times 0 + 8 \times 10 = 80 克。
- 儿童 3 收到 12 小糖果和 1 大糖果。总重量为 6 \times 12 + 8 \times 1 = 80 克。
在这种分配方式中,总共 18 大糖果已分发。
不存在满足条件且分配多于的分配方法 18 大糖果。因此,答案是 18.
示例输入 2
2 3 4 3 5
示例输出 2
-1
没有满足条件的分配方法。
示例输入 3
8 4 32 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
8000000000
答案可能不适合 32 位整数。