Suppose you want to move from 0 to 100 on the number line. In each step, you…

PYQ GATE 2014

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i,ji,j with i<ji < j. Given a shortcut (i,j)(i,j), if you are at position ii on the number line, you may directly move to jj. Suppose T(k)T(k) denotes the smallest number of steps needed to move from kk to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular, from 9 there is a shortcut to 15. Let yy and zz be such that T(9)=1+min⁡(T(y),T(z))T(9) = 1 + \min(T(y),T(z)). Then the value of the product yzyz is _____.

Attempted by 68 students.

Sign up free to check your answer

Sign up free

Explore the full course: Algorithms

Loading lesson…