Magician
Autumn Tournament (2010)
Submission name: fakir.cpp
Problem summary
A hat holds a grey, b white, c black, and d multicoloured mice. With eyes closed, how many mice must a magician draw to guarantee that every colour is represented?
Input
Four integers a, b, c, d.
Output
The minimum number of draws guaranteeing all four colours.
Constraints
1 ≤ a, b, c, d < 500.
Worked example
Original statement sample.
Input
14 9 4 7
Output
31
Solution analysis
- To avoid drawing a particular colour as long as possible, draw every mouse of the other three colours first. That permits total − count[colour] draws without that colour.
- This delay is greatest for a least numerous colour. Therefore total − minimumCount mice might still miss a colour, but one more mouse guarantees every colour.
- The sample has 34 mice, with black the smallest group of size 4. All 30 non-black mice could appear first. Draw 31 must include black and also guarantees the other colours.
Why it works
Drawing all mice except a smallest colour shows that total − minimumCount draws are insufficient. Conversely, omitting any colour allows at most total − count[colour] ≤ total − minimumCount draws. A draw count one greater makes omission of every colour impossible, proving both sufficiency and minimality.
Watch out. This is a worst-case guarantee, not the number needed in a favourable order. Add one after subtracting the smallest group.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<string>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,c,d;
cin>>a>>b>>c>>d;
int total=a+b+c+d;
int smallest=min({a,b,c,d});
// One more than all mice outside a smallest colour is necessary.
cout<<total-smallest+1<<'\n';
}