Matching Glove Chain
Autumn Tournament (2025)
Submission name: gloves.cpp
Problem summary
Students all face the teacher, so they cannot swap their left and right hands. There are A with two white gloves; B with black left and white right; C with white left and black right; D with two black gloves. Adjacent students may hold hands only when the touching gloves have equal colors. Find the largest number of students in one chain.
Input
Four integers A B C D.
Output
The maximum chain length.
Constraints
0 ≤ A,B,C,D ≤ 10^8.
Worked example
The example is reproduced from the original tournament statement.
Input
0 3 1 0
Output
3
Solution analysis
- View a student as a directed transition from the left glove color to the right glove color. Types A and D keep the color unchanged; types B and C switch it in opposite directions. Switching types must alternate in any valid chain.
- If B=C=0, a chain cannot change color, so use max(A,D). Otherwise there is a switch and both colors can be visited: include all A and D students as same-color blocks. Use 2 min(B,C) alternating switches, plus one more when B and C differ.
- For A=D=0,B=3,C=1, at most three switches alternate: B,C,B. The unused B cannot follow another B, so the answer is 3. When all four counts are 1, one chain uses every student.
Why it works
After ignoring same-color students, every chain alternates B and C, so it has at most 2 min(B,C)+1 switches, or 2 min(B,C) if their counts are equal. This bound is attained by an alternating sequence. With at least one switch that sequence visits both colors; inserting all A at a white position and all D at a black position preserves validity. Without switches only one color is available, giving max(A,D). Thus the formula is both attainable and an upper bound.
Watch out. Without any mixed-color students, A and D cannot be added together. Orientation is fixed, so excess switches of one type cannot all be used.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b==0&&c==0){
cout<<max(a,d)<<'\n';
return 0;
}
// Opposite color switches must alternate.
int switches=2*min(b,c)+(b!=c);
cout<<a+d+switches<<'\n';
}