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 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 uv 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\)

 

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
Tags:
Introduction to Dynamic Programming-2Dynamic programmingRecursionMediumAlgorithmsDynamic Programming
Points:30
11 votes
Tags:
BitmaskDynamic ProgrammingAlgorithmsApprovedMedium
Points:30
1 votes
Tags:
Introduction to Dynamic Programming-2AlgorithmsDynamic Programming