Maximum Mixed Teams
National Olympiad — Regional round (2021 season)
Submission name: teams.cpp
Problem summary
Form as many disjoint three-person teams as possible from N girls and M boys. Every team must contain both genders: either two girls and one boy or one girl and two boys.
Input
Two integers N and M.
Output
The maximum number of mixed teams.
Constraints
1 ≤ N,M ≤ 1,000,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
3 4
Output
2
Solution analysis
- Every team consumes at least one girl and one boy, so the answer cannot exceed min(N,M). It also consumes three people, giving the bound floor((N+M)/3).
- The smaller of these bounds is attainable. If one gender is scarce, use one of that gender and two of the other in each team. Otherwise distribute the third members across both genders.
- With 3 girls and 4 boys, floor(7/3) = 2 teams are possible. With 3 girls and 10 boys, the scarce-gender bound gives 3 teams, each using one girl and two boys.
Why it works
Let K = min(N,M,floor((N+M)/3)). Reserve one girl and one boy for each of K teams. The remaining N+M−2K people include at least K people in total, so one extra person can fill each team. The reserve exists because K ≤ N,M; thus K is achievable and matches the upper bound.
Watch out. Use 64-bit integers. Dividing each gender count by three separately loses possible mixed teams.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long girls, boys;
cin >> girls >> boys;
// Teams need one of each gender and three people in total.
cout << min(min(girls, boys), (girls + boys) / 3) << '\n';
}