# Magda and Silly Pairs | codechef solution

## Problem:-

Chef and his friend Magda have $2�$ mutual friends: $�$ of these friends are chefs and the other $�$ are chefettes. The chefs are numbered $1$ through $�$ and the chefettes are (independently) also numbered $1$ through $�$. Since Magda wants their friends to be as happy as possible and to preserve traditional family values, she wants to pair them up in such a way that each chef is paired with exactly one chefette and each chefette with exactly one chef.

The chefs have heights ${�}_{1},{�}_{2},\dots ,{�}_{�}$ and the chefettes have heights ${�}_{1},{�}_{2},\dots ,{�}_{�}$. For each valid $�,�$, if the $�$-th chef and the $�$-th chefette are paired, they will have exactly one child with height $⌊\frac{{�}_{�}+{�}_{�}}{2}⌋$. Magda wants to pair up the chefs and chefettes in such a way that the sum of heights of all their children ($�$ children in total) is maximum possible. Please help her do that.

### Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains a single integer $�$.
• The second line contains $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$.
• The third line contains $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$.

### Output

Print a single line containing one integer ― the maximum sum of heights of the children.

### Constraints

• $1\le �\le 10$
• $1\le �\le 1{0}^{5}$
• $1\le {�}_{�}\le 1{0}^{9}$ for each valid $�$
• $1\le {�}_{�}\le 1{0}^{9}$ for each valid $�$

Subtask #1 (40 points): $1\le �\le 100$

Subtask #2 (60 points): original constraints

Input
Output
2
3
4 5 6
1 2 3
5
4 8 6 4 1
2 5 7 4 7
10
23

### Explanation:

Example case 1: One possible solution is to pair the first chef with the second chefette, the second chef with the first chefette and the third chef with the third chefette. Their children will have heights $3$$3$ and $4$, respectively.

Code(C++):-

#include <iostream>
using namespace std;

int main() {
int T;
cin>>T;
for(int test=0;test<T;test++){
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
int o1=0,o2=0;
long long sum1=0,sum2=0;
for(int i=0;i<n;i++){
sum1+=a[i];
sum2+=b[i];
if(a[i]%2==1){
o1++;
}
if(b[i]%2==1){
o2++;
}
}
long long ans=sum1+sum2;
if(o1>o2){
ans-=o1-o2;
}
else{
ans-=o2-o1;
}
ans/=2;
cout<<ans<<endl;
}
return 0;
}

Code(Java):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int i = 0;i<t;i++){
int n = in.nextInt();
long arr1[] = new long[n];
//long arr2[] = new long[n];
long a1 = 0,a2 = 0;
long sum = 0;
for(int j = 0;j<n;j++){
arr1[j] = in.nextLong();
sum += arr1[j];
if(arr1[j]%2==0){
a1++;
}
}
for(int j = 0;j<n;j++){
arr1[j] = in.nextLong();
sum += arr1[j];
if(arr1[j]%2==0){
a2++;
}
}
sum = sum/2;
long dif = (long) (Math.abs(a1-a2)/2);
System.out.println(sum-dif);
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-