Матч 358, Сломанные кнопки (BrokenButtons)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Вы хотите установить страницу page в телетексте. Однако на устройстве управления некоторые кнопки сломаны (они задаются в массиве broken). Вы можете перейти на любую страницу, которую можете ввести при помощи устройства управления, а дальше двигаться нажимая кнопки ‘+’ (вперед) и ‘-‘ (назад). Сначала телетекст установлен на странице 100. Необходимо найти наименьшее количество нажатий на кнопки пульта управления, чтобы установить страницу page.

Класс: BrokenButtons

Метод: int minPresses(int page, vector<int> broken)

Ограничения: 0 £ page £ 500000, broken содержит от 1 до 10 разных чисел от 0 до 9.

Вход. Номер страницы page и массив broken, содержащий неработающие кнопки.

Выход. Наименьшее количество нажатий, требуемых для установки канала page.

Пример входа

page	broken
5457	{6,7,8}
100	{1,0,5}
1	{1,2,3,4,5,6,7,8,9}

Пример выхода

6

0

2

РЕШЕНИЕ

полный перебор

Создадим массив v, в котором v[i] = 1, если кнопка доступна для нажатия и v[i] = 0 иначе. Функция length(i) возвращает количество цифр в числе i. Функция canbe(x) возвращает 1, если число x может быть набрано при помощи пульта управления.

Перебираем все возможные страницы от 0 до 999999, куда изначально следует перейти при помощи пульта управления. После чего следует нажимать на кнопки ‘+’ или ‘-‘, пока не дойдем до страницы page. Дя перехода от страницы i до страницы page следует нажать abs(i – page) раз на кнопку ‘+’ или ‘-‘, а также ввести само число i, потратив на это length(i) нажатий.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

vector<int> v(10,1);

int length(int i)

{

return (i < 10) ? 1 : 1 + length(i / 10);

}

int canbe(int x)

{

do

{

if (!v[x%10]) return 0;

x /= 10;

} while(x);

return 1;

}

class BrokenButtons

{

public:

int minPresses(int page, vector<int> broken)

{

int i, res, temp;

for(i = 0; i < broken.size(); i++)

v[broken[i]] = 0;

res = abs(page - 100);

for(i = 0; i < 1000000; i++)

{

temp = abs(i - page) + length(i);

if ((temp < res) && (canbe(i))) res = temp;

}

return res;

}

};