Customising the Track Codeforces Solution

by

Customising the Track Solution

Highway 201 is the most busy street in Rockport. Traffic cars cause a lot of hindrances to races, especially when there are a lot of them. The track which passes through this highway can be divided into nn sub-tracks. You are given an array aa where aiai represents the number of traffic cars in the ii-th sub-track. You define the inconvenience of the track as ∑i=1n∑j=i+1n|ai−aj|∑i=1n∑j=i+1n|ai−aj|, where |x||x| is the absolute value of xx.

See Also: Codeforces Round 730 (Div. 2)

You can perform the following operation any (possibly zero) number of times: choose a traffic car and move it from its current sub-track to any other sub-track.

Find the minimum inconvenience you can achieve.Input

The first line of input contains a single integer tt (1≤t≤100001≤t≤10000) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.Output

For each test case, print a single line containing a single integer: the minimum inconvenience you can achieve by applying the given operation any (possibly zero) number of times.

Example

input

3
3
1 2 3
4
0 1 1 0
10
8 3 6 11 5 2 1 7 10 4

output

0
4
21

Note

For the first test case, you can move a car from the 33-rd sub-track to the 11-st sub-track to obtain 00 inconvenience.

For the second test case, moving any car won’t decrease the inconvenience of the track.

Solution

#include<bits/stdc++.h>
using namespace std;
void process()
{
	long long n;
	cin>>n;
	long long s=0;
	for(long long i=1;i<=n;i++)
	{
		long long u;
		cin>>u;
		s+=u;
	}
	s=s%n;
	cout<<s*(n-s)<<"\n";
}
int main()
{
	long long t;
	cin>>t;
	for(long long i=1;i<=t;i++)
	process();
}

Codeforces Round #730 (Div. 2)

July Long Challenge 2021 Solutions

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+