e-olymp 6. Путёвки

Постановка задачи

e-olymp 6. Путёвки

Туристическая фирма не успела из-за больших морозов продать [latex]n[/latex] ([latex]n < 15[/latex]) путёвок на горнолыжные базы, срок действия которых уже наступил. С целью уменьшения убытков, было решено с 1 февраля все такие путёвки, которым осталось [latex]d_k[/latex] ([latex]d_k \le 30[/latex]) дней, продавать по номинальной стоимости – по [latex]c_k[/latex] ([latex]c_k \le 100[/latex]) грн за день только за те дни, что остались со дня продажи ([latex]k = 1..n[/latex]).

На какую наибольшую сумму можно реализовать эти путёвки, если каждый день продавать по одной путёвке?

Входные данные

Первая строка содержит количество путёвок [latex]n[/latex]. Каждая из следующих [latex]n[/latex] строк содержит два числа – количество дней [latex]d_k[/latex] и стоимость дня [latex]c_k[/latex].

Выходные данные

Максимальная сумма прибыли.

Алгоритм решения

Решим эту задачу полным перебором (методом грубой силы). Для этого необходимо перебрать все возможные варианты реализации. К примеру, дано три путевки:

Первая путёвка

  • срок действия: 2
  • номинальная стоимость: 13

Вторая путёвка

  • срок действия: 1
  • номинальная стоимость: 33

Третья путёвка

  • срок действия: 3
  • номинальная стоимость: 7

Надо перебрать все возможные варианты и для каждого подсчитать сумму за реализованные путевки.

Путевки Перебор всех возможных вариантов
Вариант 1 Вариант 2
Очередность Результат Очередность Результат
Первая 1 20 1 20
Вторая 2 3
Третья 3 2
Вариант 3 Вариант 4
Очередность Результат Очередность Результат
Первая 2 53 2 20
Вторая 1 3
Третья 3 1
Вариант 5 Вариант 6
 Очередность Результат Очередность Результат
Первая 3 40 3 7
Вторая 1 2
Третья 2 1

Теперь очевидно, что максимальная сумма прибыли равна 53. Таким образом можно решить данную задачу при любых входных данных. Но возникает проблема, когда путевок слишком много (или даже не очень). Количество перестановок для [latex]n[/latex] элементов равно [latex]n![/latex]. Это значит, что при количестве путевок, равном [latex]14[/latex] (максимальное возможное количество в данной задаче), количество перестановок равно [latex]14! = 87178291200[/latex], а ведь для каждой необходимо подсчитать сумму за реализованые путевки. Современные компьютеры не могут справиться с этой задачей за короткий промежуток времени, поэтому явным решением является оптимизация программы.

Давайте представим, что мы имеем две путевки, сроки действия которых равны единице. Очевидно, что одну из них мы точно не успеем реализовать, так как продав одну, срок действия другой на следующий день истечет, а, так как реализовать путевки необходимо за наибольшую сумму, то реализовать нужно ту, чья номинальная стоимость выше. Отсюда следует, что, когда есть две путевки, сроки действия которых равны единице, более дешевую можно игнорировать. Теперь, пусть у нас есть три путевки, сроки действия которых равны двум. Аналогично рассуждая, можно прийти к выводу, что в такой ситуации путевку с самой низкой номинальной стоимостью можно игнорировать. Это же верно для четырех, пяти и т.д. путевок. Тогда нам остается перед началом полного перебора отсечь путевки, не влияющие на ответ, при этом сократив время выполнения в разы.

Тесты

Входные данные Выходные данные
4
2 37
3 45
1 46
4 30
232
3
1 1
2 2
3 3
11
4
1 2
3 4
5 6
7 8
84

Реализация

ideone: ссылка
Засчитаное решение: ссылка

А1035

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

Входные данные Выходные данные
a1

b1

a1
b3
d2
b1
a1
h8
a1
c2
e3
g2
h4
g6
h8

 

Решение

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard  сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.