Four Boxes
Autumn Tournament (2014)
Submission name: game.cpp
Problem summary
Four boxes contain distinct numbers from 1 to 4 or zero for an empty box. At least two boxes are filled. If one box is empty, report its position and its missing number. If two are empty, report the two missing numbers in increasing order. If none is empty, report the contents of the first two boxes.
Input
Four integers describing boxes 1 through 4.
Output
Two integers according to the three cases above.
Constraints
Each entry is 0..4; nonzero entries are distinct; at most two entries are zero.
Worked example
Original statement sample.
Input
2 0 4 1
Output
2 3
Solution analysis
- Mark every nonzero number as present and remember the positions containing zero. There are only four possible numbers, so a boolean array is sufficient.
- Scan numbers 1 through 4 in increasing order to collect the missing ones. Their count equals the number of empty boxes. Use that count to choose the required output format.
- For 2 0 4 1, number 3 is missing and the only empty box is position 2. Therefore print 2 3. With two empty boxes the positions are not requested.
Why it works
The presence array marks exactly the numbers already placed. Therefore its unmarked numbers are exactly those that must fill empty boxes. Scanning in increasing order supplies the requested order for two empty boxes; the other branches directly implement the stated cases.
Watch out. Box positions are one-based. With no empty boxes, preserve the original order of the first two values.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int box[4];
bool used[5]={};
int emptyPosition=0;
for(int i=0;i<4;++i){
cin>>box[i];
if(box[i]==0){
emptyPosition=i+1;
}
else{
used[box[i]]=true;
}
}
vector<int>missing;
for(int value=1;value<=4;++value){
if(!used[value]){
missing.push_back(value);
}
}
// The output meanings differ with the number of empty boxes.
if(missing.empty()){
cout<<box[0]<<' '<<box[1]<<'\n';
}
else if(missing.size()==1){
cout<<emptyPosition<<' '<<missing[0]<<'\n';
}
else{
cout<<missing[0]<<' '<<missing[1]<<'\n';
}
}