Hungry Mice in Two Directions
Autumn Tournament (2012)
Submission name: mice.cpp
Problem summary
All mice move left, or all move right, without passing one another. In case A each mouse eats the first uneaten cheese it encounters and then eats no more. In case B it eats every encountered uneaten piece. For each case, report the direction leaving fewer hungry mice, using D for a tie. Mice may share positions with cheese; several pieces can occupy one position.
Input
M and M mouse positions; N and N cheese positions.
Output
Two rows, one per case: L, R or D followed by the minimum hungry count.
Constraints
1 ≤ M,N ≤ 100000; positions are positive integers; mouse positions are distinct. The statement gives no explicit numeric upper bound for positions.
Worked example
Original statement sample.
Input
6 2 3 8 9 11 12 5 1 4 6 7 10
Output
L 1 L 3
Solution analysis
- Sort mice and cheese positions. For leftward motion, process mice from left to right: the leading mouse is processed before followers. Only cheese at or to the left of the current mouse can feed it. The rightward computation is the mirror image, scanning from right to left.
- In case A, count one available piece for a fed mouse. A two-pointer matching scan gives the fed count: when the next piece is reachable, consume one; otherwise this mouse must remain hungry. This assignment is a counting device, not necessarily the literal nearest piece eaten: reachability sets are nested for following mice, so changing which reachable piece is assigned does not change the total fed count. In case B, the leading mouse consumes every still-available reachable piece, so advance the cheese pointer past all of them but count only one fed mouse.
- Equality is reachable: a mouse can eat cheese on its own starting position. This matters when positions contain multiple pieces. Perform all four scans independently, then print L or R for the lower hungry count and D when equal.
- In sample case B moving left, mice at positions 2,8,11 eat the groups {1},{4,6,7},{10}; the others stay hungry, giving three. Moving right leaves four hungry, so the second output is L 3. In case A moving left feeds five of six mice.
Why it works
For case A, ordered matching is optimal by exchange: assigning the earliest available reachable cheese to the leading mouse cannot reduce what remains possible for later mice, and a mouse with no reachable piece cannot be fed. For case B, processing leading mice first assigns every piece to the first mouse that can encounter it; consuming all reachable pieces implements exactly that rule. Mirroring the order proves the rightward scans as well.
Watch out. Do not discard duplicate cheese positions. Include equality in the reachability test. Case B may consume many pieces while feeding just one mouse. Calculate cases and directions from independent pointers. D means equal hungry counts in both directions.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int hungryCount(const vector<long long>&mice,const vector<long long>&cheese,bool left,bool eatAll){
int mouseCount=static_cast<int>(mice.size());
int cheeseCount=static_cast<int>(cheese.size());
int nextCheese=left?0:cheeseCount-1;
int step=left?1:-1;
int fed=0;
for(int processed=0;processed<mouseCount;processed++){
int index=left?processed:mouseCount-1-processed;
auto reachable=[&](){
return nextCheese>=0&&nextCheese<cheeseCount&&
(left?cheese[nextCheese]<=mice[index]:cheese[nextCheese]>=mice[index]);
};
if(reachable()){
fed++;
nextCheese+=step;
// In case B this mouse eats the entire remaining reachable group.
if(eatAll){
while(reachable()){
nextCheese+=step;
}
}
}
}
return mouseCount-fed;
}
void printChoice(int left,int right){
if(left==right){
cout<<"D "<<left<<'\n';
}
else if(left<right){
cout<<"L "<<left<<'\n';
}
else{
cout<<"R "<<right<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
int n;
cin>>m;
vector<long long>mice(m);
for(long long&position:mice){
cin>>position;
}
cin>>n;
vector<long long>cheese(n);
for(long long&position:cheese){
cin>>position;
}
sort(mice.begin(),mice.end());
sort(cheese.begin(),cheese.end());
printChoice(hungryCount(mice,cheese,true,false),hungryCount(mice,cheese,false,false));
printChoice(hungryCount(mice,cheese,true,true),hungryCount(mice,cheese,false,true));
}