Matching Shoes and Bags
Национална олимпиада - Областен кръг 2026
Submission name: fashion.cpp
Problem summary
There are N white shoes, M black shoes, K white bags and T black bags. Draw X shoes and Y bags blindly, with X,Y positive. Guarantee at least one matching-colour shoe and bag while minimizing X+Y; break ties by maximizing X.
Input
N M K T.
Output
Optimal X Y.
Constraints
Each count is between 0 and 10^9; a matching colour exists in the wardrobe.
Worked example
The worked example illustrates the rule described in the analysis.
Input
10 10 10 10
Output
11 1
Solution analysis
- A failure consists of drawing only white shoes and only black bags, or only black shoes and only white bags. For a fixed X, the first failure remains possible when X≤N and Y≤T; the second when X≤M and Y≤K.
- Therefore the smallest sufficient Y is max(1,T+1 if X≤N,K+1 if X≤M). Discard it if there are not enough bags.
- This required Y changes only when X passes N or M. It is enough to test X=1,N+1,M+1, discarding impossible shoe counts. Compare total counts and apply the larger-X tie rule.
- For ten items of each colour and kind, eleven shoes force both colours. One bag then matches, giving 11 1; the equally small opposite choice loses the tie.
Why it works
The two monochromatic failures exhaust all ways of having no colour in common. The formula excludes both. Between successive threshold values, required Y is constant, so the smallest X in that region is optimal. The three candidates cover all regions.
Watch out. Allow zero counts of a colour. Require both draw counts positive and within available totals. Apply the tie rule explicitly.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The two monochromatic failures exhaust all ways of having no colour in common. The formula
// excludes both.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
long long whiteShoes,blackShoes,whiteBags,blackBags;
cin>>whiteShoes>>blackShoes>>whiteBags>>blackBags;
long long bestX=0,bestY=0,bestTotal=9000000000000000000LL;
for(long long x:{1LL,whiteShoes+1,blackShoes+1}){
if(x>whiteShoes+blackShoes){
continue;
}
long long y=1;
if(x<=whiteShoes){
y=max(y,blackBags+1);
}
if(x<=blackShoes){
y=max(y,whiteBags+1);
}
if(y>whiteBags+blackBags){
continue;
}
if(x+y<bestTotal||(x+y==bestTotal&&x>bestX)){
bestTotal=x+y;
bestX=x;
bestY=y;
}
}
cout<<bestX<<' '<<bestY<<'\n';
}