Придумай задачу по программированию на тему детской игры "Вавилонская башня"
- User
Придумай задачу по программированию на тему детской игры "Вавилонская башня"
- Assistant
Задача на программирование: "Вавилонская башня"
Описание игры: Игра "Вавилонская башня" состоит из серии блоков различной формы, которые игроки должны поочерёдно ставить друг на друга, стремясь построить как можно более высокую башню, не допуская её падения.
Цель задачи: Требуется написать программу, которая будет анализировать возможность построения стабильной башни из данных блоков и определяет максимальную высоту башни, которая может быть построена с использованием этих блоков.
Условия:
- Каждый блок описывается тремя параметрами: длина (L), ширина (W) и высота (H), все из которых являются положительными целыми числами.
- Блок может быть размещён на другой блоке, только если его длина и ширина строго меньше длины и ширины блока ниже.
- Блоки можно вращать, выбирая любую из граней в качестве основания.
- Идеально стабильной считается башня, каждый этаж которой целиком размерами меньше нижележащего.
- Задача не учитывает баланс башни или вес блоков, фокусируясь исключительно на размерах.
Входные данные:
- Первая строка содержит одно целое число N — количество блоков.
- Следующие N строк содержат по три целых числа, разделённых пробелами, описывающие размеры каждого блока (L, W, H).
Выходные данные:
- Программа должна выводить одно целое число — максимальную высоту башни, которую можно построить из предложенных блоков.
Пример входных данных: 6 5 2 3 8 5 1 7 3 2 6 3 4 4 2 2 9 7 3
Пример выходных данных: 10
Объяснение к примеру: Можно построить башню из трёх блоков с размерами (5, 2, 3), (7, 3, 2) и (9, 7, 3) для достижения максимальной высоты 10. Блоки вращать не требуется.
Замечания: Задача может быть решена с помощью динамического программирования, где каждый блок может быть использован в трёх различных ориентациях. Необходимо искать максимум из всех возможных комбинаций размеров для каждого блока, строить на их основе все возможные "этажи" башни и определять максимально возможную высоту.
- User
Сгенерируй для этой задачи 3 примера входных данных
- Assistant
Пример 1:
4 3 3 3 1 1 1 2 2 2 4 4 4Пример 2:
5 5 4 1 3 2 3 6 1 2 2 3 4 4 2 1Пример 3:
7 2 2 5 4 3 2 1 1 3 3 1 4 3 5 1 4 6 2 5 3 3