Computer Sciences > GATE 2014 SET-3 > Dynamic Programming
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, 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 _________.

Correct : 150

Similar Questions

Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required t...
#544 Fill in the Blanks
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] de...
#1044 MSQ
Consider two strings A = ""qpqrr"" and B = ""pqprqrp"". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and l...
#1269 Fill in the Blanks

Related Topics

number line movement GATE computer science 2014 shortcut number line T(k) function minimum steps to 100 computer science gate optimal path problem shortest distance on number line GATE set 3 question 44

Unique Visitor Count

Total Unique Visitors

Loading......