Dial Maximum
Practice
0 (0 votes)
Medium
Dynamic programming
Arrays
2d
Introduction to dynamic programming 2
Algorithms
Medium
Dynamic programming
Problem
61% Success 834 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Consider a dial pad of 1 to 9 digits as shown in the figure. You can not press a single digit 2 times consecutively. If you are pressing any digit, then after pressing that digit, you can only press its adjacent digit. Two digits are adjacent if they share an edge.
Cost of pressing a digit after another adjacent digit is given. Initially, you have X unit(s) of money. You need to maximize the sum of digit(s) you can press in X unit(s) of money. You can start from any digit.
Input :
- The first line of input contains an integer X, denoting amount of money you have.
- Each of the following 12 lines contains u, v and w, where w is the cost of changing digit from u to v or v to u.
Output :
- A single integer representing the maximum sum of numbers you can press in X unit of money.
Constraints :
- \(1 \le X,w \le 10^{5}\)
- \(1 \le u ,v \le 9\)
Submissions
Please login to view your submissions
Similar Problems
Points:30
Tags:
Medium
2.Reach N
Points:30
4 votes
Tags:
AlgorithmsIntroduction to Dynamic Programming-2Dynamic Programming
Points:30
Tags:
Introduction to Dynamic Programming-2Dynamic programmingRecursionMediumAlgorithmsDynamic Programming
Editorial