/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
あなたは小さな飴と大きな飴の 2 種類の飴を無尽蔵に持っています。 小さな飴の重量は X グラム、大きな飴の重量は Y グラムであり、小さな飴よりも大きな飴のほうが重い (すなわち、X < Y) です。
N 人の子供がいます。子供たちには 1 から N までの番号が付けられています。
あなたは、以下の条件を満たすように飴を配ることにしました。
- i=1,\dots,N について、子供 i には 2 種類の飴を合計でちょうど 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
答えは 32bit 整数に収まらないことがあります。
Score : 350 points
Problem Statement
You have an unlimited supply of two types of candies: small candies and large candies. The weight of a small candy is X grams, and the weight of a large candy is Y grams. Large candies are heavier than small candies (that is, X < Y).
There are N children, numbered 1 to N.
You have decided to distribute candies so that the following conditions are satisfied:
- For i=1,\dots,N, child i receives exactly A_i candies in total of the two types.
- The total weights of candies distributed to the N children are all equal.
Determine whether there exists a distribution method that satisfies the conditions. If it exists, find the maximum possible value for the number of large candies distributed.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X < Y \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N X Y A_1 \dots A_N
Output
If there is no distribution method that satisfies the conditions, output -1.
If there exists a distribution method that satisfies the conditions, output the maximum possible value for the number of large candies distributed in such a distribution method.
Sample Input 1
3 6 8 11 10 13
Sample Output 1
18
You can distribute candies as follows so that the total weights of candies distributed to the children are all equal.
- Child 1 receives 4 small candies and 7 large candies. The total weight is 6 \times 4 + 8 \times 7 = 80 grams.
- Child 2 receives 0 small candies and 10 large candies. The total weight is 6 \times 0 + 8 \times 10 = 80 grams.
- Child 3 receives 12 small candies and 1 large candy. The total weight is 6 \times 12 + 8 \times 1 = 80 grams.
In this distribution method, a total of 18 large candies are distributed.
There is no distribution method that satisfies the conditions and distributes more than 18 large candies. Therefore, the answer is 18.
Sample Input 2
2 3 4 3 5
Sample Output 2
-1
There is no distribution method that satisfies the conditions.
Sample Input 3
8 4 32 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
8000000000
The answer may not fit in a 32-bit integer.