HW2B - Editorial

editorial
, , , ,
1

PROBLEM LINK:
Practice
Source

Author: SQU_Test

DIFFICULTY:
EASY

PREREQUISITES:
Basic programming, sum, sequential search.

PROBLEM:
There are n balls (n is even) in the box. Each ball has a positive integer written on it. n / 2 people will play new ball game. At the beginning of the game each player gets two balls, each ball is given to exactly one player.

Find the way to distribute balls such that the sum of values written on the balls will be equal for each player. It is guaranteed that it is always possible.

EXPLANATION:
You can calculate the sum (x) of a pair of balls.
X = 2 * (a_1 + a_2 + ... + a_n) / n
For every card a_i, find a ball a_k which a_i + a_k = X and k is not used.
n is small, so you can simply write an O(n^2) solution.

TIME COMPLEXITY:
Time complexity of the solution is O(n^2).

SOLUTIONS:

Setter’s Solution 
n = int(input())
c = list(map(int, input().split()))
tot = (2 * sum(c))// n
b = [0]*n 
for i in range(n):
  if b[i] == 0:
    for j in range(i+1,n):
	    if b[j] == 0 and c[j] == tot – c[i]:
		    print(i+1, j+1)
		    b[i] = 1
		    b[j] = 1
2

#include
using namespace std;

int main() {
int n;
cin>>n;
int arr[n],sum=0,l=n/2;
for(int i=0;i<n;i++)
{
cin>>arr[i];
sum=sum+arr[i];
}
sum=sum/l;
for(int i=0;l>0;i++)
{
for(int j=1;j<n;j++)
{
if(arr[i]+arr[j]==sum&&arr[i]!=0&&arr[j]!=0&&i!=j)
{
cout<<i+1<<" "<<j+1<<endl;
arr[i]=0;arr[j]=0;
l–;
}
}
}
// your code goes here
return 0;
}