PA of Algorithms Q123

123Suppose 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, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k 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 y and z be such that T(9) = 1 + min (T(y), T(z)). Then the value of the product yz is_______.

Option : A
Explanation :
By definition, T(9) = Dist. From 9 to 100 As given, T(9) = 1+min (T(y), T()(z) = 1 + min (Dist. from y to 100, Dist. From z to 100)
⇒ 1 = Dist. from 9 to y/Dist. From 9 to z
⇒ There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15.
⇒ Therefore, y and z are 10 and 15 (in any order)
⇒ Product yz = 150.

Forgot your password?

I agree with the Terms.