BrokenButtons
SRM 358 · 2007-07-17 · by icanadi
SRM 358 · 2007-07-17 · by icanadi · Brute Force, Simple Math
Problem Statement
Problem Statement
You want to see some page on the teletext (information service on TV where we refer to pages of information by numbers). Unfortunately, some of the digit buttons on the remote control are broken. But you have an idea! If you can't enter the number of the page you want to see, you could enter some other number and with the buttons '+' and '-' (which are not broken) navigate to the desired page. Button '+' increases the number by 1 and button '-' decreases the number by 1. You are initially at page 100. To go to a different page, you may enter the page number using the digit buttons that aren't broken. Then, press the '+' and '-' buttons to navigate to your desired page.
You will be given an int page, the page you want to see, and aint[] broken, the list of broken digit buttons. Return the minimum number of button presses required to navigate to the page.
You will be given an int page, the page you want to see, and a
Constraints
- page will be between 0 and 500,000, inclusive.
- broken will contain between 0 and 10 elements, inclusive.
- Each element of broken will be between 0 and 9, inclusive.
- All elements of broken will be distinct.
Examples
0)
5457
{ 6, 7, 8 }
Returns: 6
You can go to page 5457 either by pressing "5455++" or "5459--".
1)
100
{ 1, 0, 5 }
Returns: 0
If you don't enter anything you'll get page 100.
2)
99999
{ 0, 2, 3, 4, 5, 6, 7, 8, 9 }
Returns: 11118
3)
158
{ 1, 9, 2, 5, 4 }
Returns: 58
4)
151241
{ 0, 1, 2, 3, 4, 7, 8, 9 }
Returns: 84580
8)
1
{1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 2
We can enter page 0.
Submissions are judged against all 150 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BrokenButtons with a public method int minPresses(int page, vector<int> broken) · 150 test cases · 2 s / 256 MB per case