Задачки ШАД на YaC 2013(решение 4 и 5 задачи)

Наконец-то дорешал задачки ШАД (YaC 2013)


Задача 4 Путники в Сахаре

4 исследователя запаслись 40 пайками и отправляются в экспедицию в Сахару. Каждый может нести запас провианта и воды на 10 дней. Цель экспедиции - наиболее далеко продвинуться в глубь пустыни, т.е. хотя бы один исследователь должен продвинуться как можно дальше, и все они должны вернуться обратно. Путешественники совершают переходы в течение дня, а вечером могут передавать друг другу провиант, а также строить хранилища пайков. Как далеко сможет пробраться экспедиция(в пересчете на дневные переходы).

Эту задачу можно классифицировать как разновидность задачи о рюкзаке. Решал я ее методом перебора.
Для начала попробовал рассмотреть задачу для двух исследователей и 20 пайков. Оптимальная стратегия выглядит так:

Исследователь 1	1	2
Исследователь 2	1	2	3	4	5	6	7

К вечеру второго дня оба исследователя имеют 8 пайков. Первый передает второму 2 пайка, оставляет 2 пайка на обратную дорогу первому и сам тратит 2 пайка чтобы вернуться. Имея 10 пайков(8 + 2) второй исследователь сможет продвинуться еще на 5 дней вперед и потом, взяв из тайника 2 пайка оставленных первым исследователем, вернуться домой.

Итого: можно максимально продвинуться на 7 переходов и еще остается 2 неиспользованных пайка.

Рассмотрим теперь задачу для трех исследователей:

Вот оптимальная стратегия

Исследователь 1	1	2
Исследователь 2	1	2	3	4
Исследователь 3	1	2	3	4	5	6	7	8	9

На второй день у всех путников остается по 8 пайков. Первый исследователь оставляет 4 пайка второму и третьему на обратный путь(по два дня), дает 2 пайка третьему и оставляет себе 2 на обратную дорогу. К третьему дню мы имеем у второго и третьего исследователей по 8 и 10 пайков соответственно, для которых мы выбираем вышеуказанную стратегию. Плюс мы не имеем издержек в виде двух неиспользованных пайков.

Итого: можно продвинуться вглубь пустыни на 9 переходов.

Теперь рассмотрим исходную задачу:

Оптимальная стратегия

Исследователь 1	1	2
Исследователь 2	1	2	3
Исследователь 3	1	2	3	4	5
Исследователь 3	1	2	3	4	5	6	7	8	9	10

После второго дня первый исследователь имеет 8 пайков, два он оставляет себе на обратную дорогу и 6 оставляет на обратную дорогу остальным трем исследователем.

К началу третьего дня 2,3,4 исследователи имеют по 8 пайков. Они делают один дневной переход и имеют по 7 пайков. Второй исследователь откладывает один паек себе и 2 на обратную дорогу для всех оставшихся за 3 день. А оставшиеся 4 раздает третьему и четвертому чтобы они вышли на уже знакомую нам раскладку в 8 и 10 пайков с помощью которой они продвинутся еще на 7 дней вглубь.

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

Задача 5 Чай вприкуску

К купчихе Капитолине Львовне пришли гости, и она пригласила их пить чай с сахаром вприкуску. Поставила самовар, достала сахар и обнаружила, что сахар отсырел, и все 27 кубиков слиплись в один большой куб. Капитолина Львовна уже хотела расколоть кусок сахара, но капризные гости сказали, что они не желают пить чай с кубиками сахара, а хотят, чтобы кусочки были какой-нибудь необычной формы(т.е. фигурками, составленными из кубиков, но не являющимися прямоугольными параллелепипедами). К тому же гости захотели, чтобы все кусочки сахара были разной формы(фигурки считаются разными, если их можно совместить только при отражении, но нельзя при повороте). Зато они обещали не обижаться, если им достанется разное количество кубиков. Немного поразмышляв, Капитолина Львовна все же выполнила прихоть гостей. А про себя подумала: "Вот если бы еще кто-нибудь пришел в гости, то тогда уж точно задача была бы невыполнимой!". Сколько же гостей пришло к Капитолине Львовне, если сама она сладкого не ела.

Хотя я и решил эту задачу, все же не использовал одно из условий, поэтому есть подозрения что что-то было упущено. Вот оно: "фигурки считаются разными, если их можно совместить только при отражении, но нельзя при повороте".
Для начала я попытался прикинуть какими типами фигурок я вообще могу располагать.
3-х элементные:
4-х элементные:

На мой взгляд поворачивая данные фигурки в разных плоскостях я перекрою все виды четырехэлементных фигурок.

Весь наш исходный куб состоит их 27 кубиков. Вышеуказанными тремя мы используем 11 кубиков. Останется еще 16. Их можно просто подобрать из двух 5 элементных и одного 6 элементного.

Итого мы сможем разбить данных куб всего лишь на 6 фигурок. Получается в гости пришло 6 гостей.