Вступление
После долгой битвы вам удалось победить Сфинкса в конкурсе загадок. Сфинкс, впечатленный вашим умением, желает дать вам награду, соразмерную с вашим умом, и создает полосу магического пергамента, разделенную на восемь коробок, каждая из которых содержит цифру.
«Сложите пергамент, - говорит Сфинкс, - так, чтобы коробки перекрывались, и эти коробки будут сливаться либо путем сложения, либо умножения. Когда останется один ящик, его ценность будет вашей наградой в золотых монетах».
задача
Вы должны написать программу или функцию, которая принимает в качестве входных данных список / массив / что угодно из восьми натуральных чисел и возвращает / печатает максимально возможное вознаграждение, получаемое в результате серии операций «складывания».
механика
«Складка» операция выполняется на некотором количестве клеток, и с любым +
или в *
качестве оператора. Первые n ячеек списка сворачиваются и объединяются с ячейками назначения с помощью оператора. Любые ячейки, которые не используются в операции слияния, остаются неизмененными.
Вот пример складывания с использованием n = 3 ячеек:
используя любое дополнение, которое привело бы к этому:
или умножение, которое привело бы к этому:
Примечание. Для простоты запрещается сгибание с количеством ячеек, меньшим 1, а также с количеством ячеек, большим или равным длине списка. Однако список может быть увеличен более чем наполовину.
Список из 8 ячеек может быть увеличен на 5, в результате чего получится новый список длиной 5: будет
[0,1,2,3,4,5,6,7]
увеличен на 5 ячеек с использованием +
оператора [9,9,9,1,0]
.
счет
Стандартный код правил игры в гольф - код, который выдает правильный вывод и имеет наименьшее количество байтов.
Бонус: если ваш код также возвращает / печатает последовательность операций сгиба, которая приводит к максимальному вознаграждению, умножьте ваш счет на 0,8. Пример вывода может выглядеть так:
crease 5 +
crease 2 *
crease 2 +
crease 1 *
Примеры
Протестируйте ваш код, используя эти входные данные и результаты в виде input - maximum reward
:
[0, 1, 2, 3, 4, 5, 6, 7] - 7560
[0, 9, 0, 3, 2, 6, 1, 5] - 1944
[0, 1, 0, 3, 0, 2, 0, 4] - 36
[6, 0, 9, 1, 9, 0, 7, 3] - 11907
[0, 5, 2, 0, 1, 3, 8, 8] - 2560
Ответы:
Pyth, 31 байт
Это определяет функцию,
y
которая вычисляет значение складки.Демонстрация.
При этом используется рекурсивный метод, в котором берется максимальное количество баллов каждого возможного преемника.
Базовый случай рекурсии реализуется путем объединения входных данных с отсортированными значениями возможных преемников, а затем с окончанием списка результатов. Если на входе есть только 1 элемент, преемников нет, и поэтому конец списка является единственным элементом на входе.
источник
C #,
275272 байтаЭто просто рекурсивная функция, которая обходит каждую ветку и возвращает лучший результат.
Отступы для ясности:
источник