Maximize The Boxes

Last Updated on March 29, 2022 by Ria Pathak

CONCEPTS USED:

Searching, Basic Mathematics

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given chocolates of 3 types A, B, C with their frequencies f_A,f_B and f_C, you need to pack these chocolates in a box. Maximize the number of boxes for given f_A,f_B and f_C. Q queries will be asked.

See original problem statement here

CONDITIONS:

1. Box should contain exactly 3 chocolates.

2. It should contain at least 1 type of chocolate A and 1 type of chocolate B.
   Allowed : (A,B,C) , (A,A,B), (A,B,B)
   Not Allowed : (C,C,A) , (A,A,A) etc

For Example:

Input : 4 2 1

Output : 2

Explanation : Every box should have atleast 1 chocolate of type A and 1 chocolate of type B, so she have only arrangement possible - 

(A B C) => we have single C, which is used here
(A B A) => out of two B's, last B is used here

Therefore, Maximum of 2 boxes can be made.

Input : 5 4 0

Output : 3

Explanation : Every box should have at least 1 chocolate of type A and 1 chocolate of type B, so she have only arrangement possible - 

(A B A) => 3 A's and 3 B's left
(A B B) => 2 A's and 1 B left
(A A B) => all A's and B's used

Therefore, Maximum of 3 boxes can be made.

SOLVING APPROACH:

1. The approach is quite simple as there are only two cases to cover.

   1. If minimum frequency between A and B is less than or equal to frequency of C, than minimum frequency between A and B is our answer, as Chocolate A and B are essential in every box so the minimum of these two will be the result.
   2. Else if minimum frequency between A and B is greater than frequency of C, this implies that putting only 1-1 chocolate A and chocolate B are not sufficient in each box as there are insufficient chocolate C for all such boxes.
2. So, calculate the Sum of frequency of all the three boxes and divide it by 3.
3. The minimum between this Sum and minimum frequency between A and B will be our answer.

ALGORITHM:

min_f_AB = minimum of (frequency of A , frequency of B)
Sum_f_ABC = (frequency of A + frequency of B + frequency of C)/3

if (min_f_AB <= frequency of C)
    print min_f_AB
else
    if(Sum_f_ABC < min_f_AB)
        print Sum_f_ABC
    else
        print min_f_AB

ILLUSTRATION:

2 2 2

Min of A and B <= C i.e. (2 <= 2)
So, Maximum boxes is Min of A and B i.e. 2

4 2 1 

Min of A and B > C i.e. (2 > 1)
So calculate average of all frequencies and check whether it is (< Min of A and B)
sum = (A + B + C) / 3 = (4 + 2 + 1) / 3 = 2
Since, sum < Min of A and B
so sum is our Maximum number of boxes i.e. 2

SOLUTIONS:

#include <stdio.h>

int main()
{
  int q; scanf("%d", &q);
  while(q--){
    int f_a, f_b, f_c, min_ab;
    scanf("%d %d %d", &f_a, &f_b, &f_c);

    // find mininum among f_a and f_b
    if(f_a < f_b)
      min_ab = f_a;
    else
      min_ab = f_b;

    // print the minimum of (f_a, f_b) and f_c 
    if(min_ab <= f_c){
      printf("%d\n", min_ab);
    }

    /* print minimum of (sum of frequencies divided by 3) and
     (minimum of (f_a, f_b) ) */
    else{
      int sum = (f_a + f_b + f_c)/3;
      if(sum < min_ab)
        printf("%d\n", sum);
      else 
        printf("%d\n", min_ab);
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int q; cin>>q;
  while(q--){
    int f_a, f_b, f_c ;
    cin>>f_a>>f_b>>f_c ;

    // print the minimum of (f_a, f_b) and f_c 
    if(min(f_a, f_b) <= f_c){
      cout<<min(f_a, f_b)<<"\n";
    }

    /* print minimum of (sum of frequencies divided by 3) and
     (minimum of (f_a, f_b) ) */
    else{
      int sum = (f_a + f_b + f_c)/3;
      cout<<min(sum, min(f_a, f_b)) <<"\n";
    }
  }
  return 0;
}

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

public class Main {
  public static void main(String args[]) throws IOException {

    Scanner sc = new Scanner(System.in);
    int q = sc.nextInt();

    while(q != 0){
      int f_a = sc.nextInt();
      int f_b = sc.nextInt();
      int f_c = sc.nextInt();

      // print the minimum of (f_a, f_b) and f_c 
      if(Math.min(f_a, f_b) <= f_c){
        System.out.println(Math.min(f_a, f_b));
      }

      /* print minimum of (sum of frequencies divided by 3) and
     (minimum of (f_a, f_b) ) */
      else{
        int sum = (f_a + f_b + f_c)/3;
        System.out.println(Math.min(sum, Math.min(f_a, f_b)));
      }
      q--;
    }
  }
}

[forminator_quiz id="1102"]

This article tried to discuss the concept of Searching, Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming