For a given array a consisting of n integers and a given integer m find if it is…
- User
For a given array a consisting of n integers and a given integer m find if it is possible to reorder elements of the array a in such a way that ∑{i=1}^{n}{∑{j=i}^{n}{(a_j)/(j)}} equals m? It is forbidden to delete elements as well as insert new elements. Please note that no rounding occurs during division, for example, 5/2=2.5. Input
The first line contains a single integer t — the number of test cases (1 ≤ t ≤ 100). The test cases follow, each in two lines.
The first line of a test case contains two integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 10^6). The second line contains integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^6) — the elements of the array.
Output
For each test case print "YES", if it is possible to reorder the elements of the array in such a way that the given formula gives the given value, and "NO" otherwise.
Example
Input
2 3 8 2 5 1 4 4 0 1 2 3
Output
YES NO
Note
In the first test case one of the reorders could be [1, 2, 5]. The sum is equal to (1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5/3) = 8. The brackets denote the inner sum ∑_{j=i}^{n}{(a_j)/(j)}, while the summation of brackets corresponds to the sum over i.
Assistant
We need to understand the problem: Given array a of n integers, we can reorder them arbitrarily. Compute the sum S = ∑{i=1}^{n} ∑{j=i}^{n} (a_j)/j. Note that division is exact rational, not integer division (so it's floating point). We need to see if there exists a permutation of a such that S equals exactly m (which is an integer). The problem statement says no rounding occurs, but m is integer, but S might be rational. However, it's asking if S equals m exactly. The inputs are integers, so S is sum of a_j / j multiplied by some coefficient. Let's derive expression.
S = ∑{i=1}^{n} ∑{j=i}^{n} a_j / j = ∑{j=1}^{n} (a_j / j) * (number of i such that i ≤ j). For each j, i can be 1,...,j, so count = j. So S = ∑{j=1}^{n} a_j / j * j = ∑{j=1}^{n} a_j. Wait that seems too trivial: because inner sum includes a_j/j for all i <= j, so each term a_j/j appears exactly j times. So S = ∑{j=1}^{n} a_j. Indeed, S = total sum of a_i? Let's check with example: For a = [1,2,5] with n=3: According to formula: compute S = (1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5/3) = 1 + 1 + 5/3 + 1 + 5/3 + 5/3? Actually compute: first bracket: 1/1=1, 2/2=1, 5/3≈1.6667 => sum=3.6667; second: 2/2=1, 5/3=1.6667 => sum=2.6667; third: 5/3=1.6667; total = 3.6667+2.6667+1.6667 = 8.0 exactly? 3.6667+2.6667=6.3334 +1.6667=8.0001? Let's compute exactly as fractions: 1/1=1, 2/2=1, 5/3; sum first = 1+1+5/3 = 2 + 5/3 = (6+5)/3=11/3? Wait 2 = 6/3 so 6/3+5/3=11/3. Second: 1 + 5/3 = 8/3. Third: 5/3. Sum = 11/3 + 8/3 + 5/3 = 24/3 = 8. So S = 8 = sum of array [1,2,5] is 8. Yes.
So indeed S = sum_{j=1}^{n} a_j regardless of ordering? Wait we used indices j as positions after reordering. In the formula, j is the index in the permuted order. S = ∑_{j=1}^{n} a_j / j * j = a_j. But careful: the coefficient for a_j is j * (1/j) = 1, regardless of position? Yes, because each a_j (at position j) contributes a_j/j per each i ≤ j, and there are j such i, so total contribution = a_j. So indeed S simplifies to sum of all elements of the array. So the sum is independent of the order! Let's check with another order: [2,5,1]. Compute: first bracket: 2/1 + 5/2 + 1/3 = 2 + 2.5 + 0.3333 = 4.8333; second: 5/2 + 1/3 = 2.5+0.3333=2.8333; third: 1/3=0.3333; total=4.8333+2.8333+0.3333=8.0? 4.8333+2.8333=7.6666+0.3333=8.0 approx. As fractions: 2/1=2, 5/2=5/2, 1/3=1/3 => sum first = 2 + 5/2 + 1/3 = (12/6 + 15/6 + 2/6)=29/6? Wait common denominator 6: 2=12/6, 5/2=15/6, 1/3=2/6, total 29/6. second: 5/2+1/3=15/6+2/6=17/6. third: 1/3=2/6. Sum = (29+17+2)/6=48/6=8. Yes.
So S always equals total sum of a_i, regardless of ordering! So the condition reduces to: Is sum of array equal to m? Because we can reorder arbitrarily, but it doesn't matter. Wait the problem asks: "find if it is possible to reorder elements of the array a in such a way that ... equals m." Since sum is invariant under reordering, the answer is YES if and only if sum(a) = m. But there's a nuance: the index j in denominator is the position after reordering. In our derivation we assumed that a_j is the element placed at position j. The sum S = ∑{i=1}^{n} ∑{j=i}^{n} a_j/j. For each fixed permutation, indeed S = ∑_{j=1}^{n} a_j (since a_j is the value at position j). So S = total sum of array. So it's invariant. So problem becomes trivial: just check if sum equals m.
But wait: In the example, they gave test: 3 8 with array 2 5 1, sum=8 => YES. Second test: 4 4 with 0 1 2 3, sum=6 => not 4, so NO. So matches.
But is there any catch? Could there be any trick like division by j might be floating point but sums to exactly total sum? Since it's rational, sum always equals integer if total sum is integer? Actually a_j are integers, so total sum is integer. The sum S computed via fractions yields exactly total sum, because we can factor: S = ∑_{j} a_j/j * j = ∑ a_j. So indeed exactly. So answer is simply if sum == m.
Given constraints t up to 100, n up to 100, a_i up to 1e6, sum could be up to 1e8? Actually n*1e6=1e8, which is okay. m up to 1e6? Wait m up to 10^6? In constraints: 0 ≤ m ≤ 10^6, but sum could be larger than 1e6? Possibly, but then S != m, so output NO. But we need to compute sum anyway. Use 64-bit.
Thus solution: For each test case, read n, m, read array, compute sum, output "YES" if sum == m else "NO". That's it.
But wait, the problem statement says "It is forbidden to delete elements as well as insert new elements." That's about reordering only. Yes.
Double-check with a weird case: n=1, a=[0], m=0 => sum=0 => YES. n=1, a=[5], m=5 => YES. n=2, a=[1,2], m=3 => YES. m=2 => NO.
Thus solution is trivial.
But maybe there is a subtlety: The denominator j is integer division? But they say "no rounding occurs during division, for example, 5/2=2.5." So it's exact division. So indeed.
Therefore answer is trivial.
Given the problem might be from a contest, the intended solution is likely to realize the simplification. So I'll code accordingly.
But wait, ensure there is no misunderstanding: The sum is defined as double sum over i and j where for each inner sum we compute a_j/j, which is the element at position j divided by j. Since a_j are placed, the sum simplifies.
Proof: ∑{i=1}^{n} ∑{j=i}^{n} a_j/j = ∑{j=1}^{n} (a_j/j) * ∑{i=1}^{j} 1 = ∑{j=1}^{n} (a_j/j) * j = ∑{j=1}^{n} a_j.
So it's correct.
Thus answer.
Now implement.
Edge Cases: none.
Let's code in C++.
Pseudo:
int t; cin>>t; while(t--){ int n, m; cin>>n>>m; long long sum = 0; for(int i=0;i<n;i++) { int x; cin>>x; sum+=x; } if(sum == m) cout<<"YES\n"; else cout<<"NO\n"; }
Note that m is integer up to 1e6, but sum can be up to 1e8, so we need long long to be safe.
Complexity O(t*n).
Thus final answer.
But wait: check constraints: t up to 100, n up to 100, so fine.
Thus I'll output solution.
However, maybe the twist: The array reorder is allowed, but maybe they mean that the index j in denominator is the original index? No, they said "reorder elements of the array a" meaning we can permute them, then compute the sum using the new order. So j is position in new order.
Thus it's correct.
Alright.
I'll produce final answer. ```cpp
#include using namespace std;
int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; long long sum = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; sum += x; } cout << (sum == m ? "YES" : "NO") << endl; } return 0; }