Company: Samsung_19nov
Difficulty: medium
Dr. Jang's Probabilistic Movement Dr. Jang spends his whole working day walking between the divisions of the company, and he keeps one rule: he stays in a division for exactly 10 minutes at a time . His movement is described by a directed graph with probabilities. He always begins the day in division 1 . Every time a 10-minute interval ends he picks exactly one outgoing arrow of the division he is in and follows it, choosing the arrow according to the probability written on it. Travelling between divisions takes no time. For every division that has at least one outgoing arrow, the probabilities written on its arrows add up to 1 . A division with no outgoing arrow is a last stop: Dr. Jang spends his 10 minutes there and then leaves work , so from that moment on he is in no division at all. Given an elapsed time T , report the division in which Dr. Jang is most likely to be exactly T minutes after he starts, together with that probability. How elapsed time works Dr. Jang has made floor(T