Header Ads Widget

Magda and Silly Pairs | codechef solution

Rajnish Tripathi 21:34

 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,…,�� and the chefettes have heights �1,�2,…,��. For each valid �,�, if the �-th chef and the �-th chefette are paired, they will have exactly one child with height ⌊��+��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,…,��.
  • The third line contains � space-separated integers �1,�2,…,��.

Output

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

Constraints

  • 1≤�≤10
  • 1≤�≤105
  • 1≤��≤109 for each valid �
  • 1≤��≤109 for each valid �

Subtasks

Subtask #1 (40 points): 1≤�≤100

Subtask #2 (60 points): original constraints

Sample 1:

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() {
    // your code goes here
    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
    {
        // your code goes here
        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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments