tg-me.com/Competitive_Programming_Cpp/53
Last Update:
Elevator Problem
A building has floors numbered 0 through n≤10^18. There is a single elevator with four buttons: "go to floor 0", "+a floors", "+b floors", and "+c floors". We have a,b,c≤ 10^6. Compute the number of unreachable floors.
Solution:
This feels like a number theory problem, but trying to solve it by GCDs and casework will not lead to success. Instead, treat it as a graph theory problem. First, note that if you can reach floor x, you can reach all floors of the form x+k*a. Hence, for each remainder modulo a all we need is the smallest reachable x with this remainder. These can be found by using Dijkstra’s shortest path algorithm on a graph with a nodes. The nodes are the remainder classes, and from each node there are two edges, corresponding to +b and +c.
The stunning thing about this problem is the asymmetry of the solution: you are treating one button differently from the other two.
Credits : Michal Forišek on Quora, scientist, competitive programmer
BY Competitive Programming
Warning: Undefined variable $i in /var/www/tg-me/post.php on line 280
Share with your friend now:
tg-me.com/Competitive_Programming_Cpp/53