Матч 340, Решение задач (ProblemsToSolve)

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

Учитель задал Вам решить определенный набор задач. Начинать решать его следует с нулевой задачи. После решения i - ой задачи Вы можете перейти к решению или (i + 1) - ой , или (i + 2) - ой задачи. Пропускать более одной задачи нельзя. Например, порядок решения {0, 2, 3, 5} приемлемый, а {0, 2, 4, 7} нет, так как расстояние между задачами 4 и 7 велико.

Массив pleasantness указывает на уровень приятности для Вас задач: чем больше pleasantness[i], тем более Вам нравится i - ая задача. Вы должны решать задачи до тех пор, пока разность приятности любых двух решенных Вами задач не станет больше или равной некоторому пороговому значению variety. Если такое никогда не случится, то задачи следует решать до конца.

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

Класс: ProblemsToSolve

Метод: int minNumber(vector<int> pleasantness, int variety)

Ограничения: pleasantness содержит от 1 до 50 элементов, 0 £ pleasantness[i] £ 100, 1 £ variety £ 1000.

Вход. Массив приятности задач pleasantness и пороговое значение variety.

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

Пример входа

pleasantness	variety
{1, 2, 3}	2
{1, 2, 3, 4, 5}	4
{6, 2, 6, 2, 6, 3, 3, 3, 7}	4

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

2

3

2

РЕШЕНИЕ

перебор

Рассмотрим все возможные пары задач (i, j), i < j, модуль разности приятности которых не меньше variety. Тогда для удовлетворения условий учителя достаточно будет решить задачи i и j. Поскольку начинать решение следует с нулевой задачи, то в таком случае следует как можно быстрее двигаться к i - ой, а потом и к j - ой задаче. Количество задач, необходимых для решения, чтобы добраться от нулевой до n - ой задачи, равно (n + 1) / 2 (не считая нулевую), его будем подсчитывать в функции calc. Тогда чтобы добраться с нулевой и решить i - ую и j - ую задачи, необходимо как минимум решить 1 + calc(i) + calc(j – i) задач.

Для каждой возможной такой пары задач (i, j) вычисляем наименьшее количество задач, которое требуется решить. Среди всех таких наименьших количеств задач находим минимум.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

int calc(int n)

{

return (n + 1) / 2;

}

class ProblemsToSolve

{

public:

int minNumber(vector<int> pleasantness, int variety)

{

int i, j, res = pleasantness.size();

for(i = 0; i < pleasantness.size() - 1; i++)

for(j = i + 1; j < pleasantness.size(); j++)

if (abs(pleasantness[i] - pleasantness[j]) >= variety)

res = min(res,1 + calc(i) + calc(j - i));

return res;

}

};