Team Formation

Find the maximum number of perfect teams that can be formed with at least one coder, one mathematician, and exactly three members

Understand the Problem

Problem Statement

Team Formation: In a class, there are three types of students. C students are coders, M are mathematicians and X students have no specialization. The values of C, M and X are passed as the input to the program. The program must print the maximum number of perfect teams that can be formed from the students in the class. A perfect team includes at least one coder, at least one mathematician and it consists of exactly three members.

Constraints

0 <= C, M, X <= 10^9
C, M, X are non-negative integers

Examples

Example 1

Input

4 4 1

Output

Explanation

First team: 1 coder + 1 mathematician + 1 X student. Remaining: 3 coders, 3 mathematicians, 0 X. Second team: 2 coders + 1 mathematician. Remaining: 1 coder, 2 mathematicians. Third team: 1 coder + 2 mathematicians. Remaining: 0 coders, 0 mathematicians. Total: 3 teams.

Example 2

Input

1 0 2

Output

Explanation

We need at least one coder and one mathematician for a perfect team. Since there are 0 mathematicians, no perfect teams can be formed.

Solution

#include <stdio.h>
#include <stdlib.h>

int main()
{
    long long c, m, x;
    scanf("%lld %lld %lld", &c, &m, &x);
    
    long long teams = 0;
    
    // First, form teams with one of each type
    long long balanced = (c < m) ? ((c < x) ? c : x) : ((m < x) ? m : x);
    teams += balanced;
    c -= balanced;
    m -= balanced;
    x -= balanced;
    
    // Then, form teams using two of the more abundant and one of the less abundant
    while (c > 0 && m > 0) {
        if (c >= m) {
            c -= 2;
            m -= 1;
        } else {
            m -= 2;
            c -= 1;
        }
        teams++;
    }
    
    printf("%lld", teams);
    return 0;
}

Time:O(min(C, M)) - The while loop runs at most min(C, M) times

Space:O(1) - Only using a constant amount of extra space

Approach:

Step-by-step explanation:

Input Reading: Read the counts of coders (C), mathematicians (M), and X students (X) as long long integers to handle large values up to 10^9.
First Phase - Balanced Teams: Calculate the minimum of C, M, and X to determine how many teams we can form with one of each type. This is the most efficient way to use X students.
Update Counts: Subtract the used students from each count.
Second Phase - Remaining Teams: While we have at least one coder and one mathematician left, form teams using two of the more abundant type and one of the less abundant type. This ensures we use up all available students efficiently.
Output: Print the total number of teams formed.

Visual Explanation

Loading diagram...

All Problems