Collect Three Pebble Piles
Autumn Tournament (2008)
Submission name: peb.cpp
Problem summary
A move selects two piles and transfers from the larger pile as many pebbles as the smaller currently has. Thus (x,y), with x≤y, becomes (2x,y−x). Equal piles can be merged. Find the minimum moves needed to put every pebble in one pile, or −1 if impossible.
Input
Three positive integers a b c.
Output
The minimum number of moves, or −1.
Constraints
a,b,c>0 and a+b+c<100.
Worked example
Original statement sample.
Input
1 2 1
Output
2
Solution analysis
- The total S never changes. Store a state as its three pile sizes sorted increasingly: pile names do not matter because the same moves are available for any pair. Only the first two sizes need to index the visited table; the third is S−first−second.
- Run breadth-first search from the sorted input. For each of the three pairs, double the smaller size and subtract it from the larger, sort the resulting triple, and enqueue it if unseen. Every move has cost one, so the first visit to [0,0,S] is optimal.
- For [1,1,2], merge the two one-pebble piles to obtain [0,2,2]. Merge the two equal nonzero piles to obtain [0,0,4], using two moves. From [1,1,3], BFS exhausts the reachable states without reaching a single nonempty pile.
Why it works
Sorting only identifies states differing by a permutation of pile labels; this does not change reachability or move count. BFS enumerates every legal transition with unit cost, so its first goal distance is the minimum. If no goal is reached, every reachable state has been examined and the task is impossible.
Watch out. The moves are directed: do not assume every transformation is reversible. A zero pile creates a no-op when selected with a larger one; the visited check safely removes it. Equal piles must be allowed to merge.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
array<int,3>start;
cin>>start[0]>>start[1]>>start[2];
int total=start[0]+start[1]+start[2];
sort(start.begin(),start.end());
vector<vector<int>>distance(total+1,vector<int>(total+1,-1));
queue<array<int,3>>pending;
pending.push(start);
distance[start[0]][start[1]]=0;
while(!pending.empty()){
auto state=pending.front();
pending.pop();
int steps=distance[state[0]][state[1]];
if(state[0]==0&&state[1]==0){
cout<<steps<<'\n';
return 0;
}
for(int first=0;first<3;first++){
for(int second=first+1;second<3;second++){
auto next=state;
// Sizes are sorted, so first is the smaller selected pile.
next[second]-=next[first];
next[first]*=2;
sort(next.begin(),next.end());
if(distance[next[0]][next[1]]==-1){
distance[next[0]][next[1]]=steps+1;
pending.push(next);
}
}
}
}
cout<<-1<<'\n';
}