CONCEPTS USED:
Searching, Basic Mathematics
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(
SIMPLIFIED)
:
Given chocolates of
3
typesA, B, C
with their frequenciesf_A
,f_B
andf_C
, you need to pack these chocolates in a box. Maximize the number of boxes for givenf_A
,f_B
andf_C
.Q
queries will be asked.
See original problem statement here
CONDITIONS:
Box should contain exactly
3
chocolates.It should contain at least
1
type of chocolateA
and1
type of chocolateB
.
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:

The approach is quite simple as there are only two cases to cover.
 If
minimum
frequency between A and B is less than or equal to frequency of C, thanminimum
frequency between A and B is our answer, as ChocolateA
andB
are essential in every box so theminimum
of these two will be the result.  Else if
minimum
frequency betweenA
andB
is greater than frequency ofC
, this implies that putting only11
chocolateA
and chocolateB
are not sufficient in each box as there are insufficient chocolateC
for all such boxes.
 If
 So, calculate the
Sum
of frequency of all the three boxes and divide it by3
.  The
minimum
between thisSum
andminimum
frequency betweenA
andB
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; } } }
where
N =
Number
of
queries
Space Complexity:
O(1)
[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