Honey Visits
Autumn Tournament (2017)
Submission name: honey.cpp
Problem summary
Pooh eats honey n times. His first meal is at Rabbit’s house. After each meal except the last, he walks directly to one of the other two houses and eats again; revisits are allowed. The Rabbit–Owl, Rabbit–Eeyore and Owl–Eeyore paths have lengths a, b and c centimetres. Minimize the total distance.
Input
Four integers n, a, b, c.
Output
Two integers: whole metres and remaining centimetres of the minimum distance.
Constraints
1 ≤ n, a, b, c ≤ 100.
Worked example
First official statement sample.
Input
3 2 3 1
Output
0 3
Solution analysis
- Keep the minimum distance for each possible current house after a fixed number of meals. Initially Rabbit costs 0 and the other houses are unreachable.
- For each next meal, try walking from each current house to either different house. Update a fresh array with the smallest resulting distance, so exactly one walk is added per meal.
- For n = 3, a = 2, b = 3, c = 1, walk Rabbit → Owl → Eeyore. The distance is 2 + 1 = 3 cm, output as 0 3. For n = 1 no walk is needed.
Why it works
Initially the states describe exactly the one-meal journeys. Every journey with one more meal consists of a valid shorter journey and a direct walk to a different house. The transitions consider all such final walks and minimize their cost, preserving the state meaning. The minimum final state is the optimal complete journey.
Watch out. The first meal already counts. Do not require returning to Rabbit. Convert centimetres only after optimization.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Initially the states describe exactly the one-meal journeys. Every journey with one more
// meal consists of a valid shorter journey and a direct walk to a different house.
#include<algorithm>
#include<array>
#include<iostream>
using namespace std;
int main(){
int n,a,b,c;
cin>>n>>a>>b>>c;
int distance[3][3]={{0,a,b},{a,0,c},{b,c,0}};
const int INF=1000000;
array<int,3>cost={0,INF,INF};
for(int meal=2;meal<=n;++meal){
array<int,3>next={INF,INF,INF};
for(int from=0;from<3;++from){
for(int to=0;to<3;++to){
if(from!=to){
next[to]=min(next[to],cost[from]+distance[from][to]);
}
}
}
cost=next;
}
int answer=*min_element(cost.begin(),cost.end());
cout<<answer/100<<' '<<answer%100<<'\n';
}