Изменить: в конце вопроса я буду награждать 100-репутацию за первый решатель бонусной головоломки !
Я добавлю награду к вопросу только тогда, когда ответ появится, поскольку эта награда не имеет крайнего срока.
Учитывая неубывающий список однозначных положительных целых чисел, вы должны определить, как глубоко в подземелье будут копаться цифры.
███ ███ A dungeon with 5 blocks removed and a depth of 3.
███ ███
███ ████
████████
Перед началом копания земля ровная.
Каждая цифра может удалить ровно один блок почвы из-под себя, но она должна достичь этой позиции снаружи подземелья, и после того, как она удалена, блок должен покинуть подземелье. При этом цифра не может опускаться или подниматься больше своего числового значения на любом шаге по горизонтали.
Цифры используют следующую стратегию копания:
- Цифра с наименьшим значением копает первые, и после этого следующий экскаватор всегда является следующим наименьшим значением из остальных цифр.
- Первая цифра может копать в любой позиции. (Вся земля одинакова.)
- Следующие цифры всегда копают в крайнем левом столбце, который уже запущен, куда они могут пойти и выйти. Если такого столбца не существует, они начинают копать новый столбец справа от самого правого.
Например, цифры 1 1 1 2 3 3
будут копать следующее подземелье (пошаговая визуализация с номерами, обозначающими, какой тип цифры выкапывает эту позицию):
███1████ ███11███ ███11███ ███11███ ███11███ ███11███
████████ ████████ ███1████ ███1████ ███1████ ███13███
████████ ████████ ████████ ███2████ ███2████ ███2████
████████ ████████ ████████ ████████ ███3████ ███3████
████████ ████████ ████████ ████████ ████████ ████████
Пояснения к примеру:
- Второй
1
не может вылезти из единственного доступного столбца, если он углубит его до2
глубины, поэтому он копает прямо в него. - Третий
1
может копаться в крайнем левом столбце, создавая столбец2
-deep, поскольку он может переместиться в1
столбец -deep и затем на уровень земли. - Следующий
2
и3
оба могут копаться в крайнем левом столбце. - Последний
3
не может копать в крайнем левом столбце, но может в следующем.
вход
- Неубывающий список положительных однозначных целых чисел хотя бы с одним элементом.
Вывод
- Одно положительное целое число, глубина построенного подземелья.
Примеры
Input => Output (с пояснениями глубин столбцов подземелья слева направо, которые не являются частью вывода)
[3] => 1
(column depths are [1])
[1, 1, 1, 2, 3, 3] => 4
(column depths are [4, 2])
[1, 1, 1, 1, 1, 1, 1, 1] => 3
(column depths are [3, 2, 2, 1])
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5] => 11
(column depths are [11, 6, 2])
[1, 1, 1, 1, 1, 2, 2, 9, 9, 9] => 7
(column depths are [7, 2, 1])
[2, 2, 2, 2, 2, 5, 5, 5, 7, 7, 9] => 9
(column depths are [9, 2])
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5] => 10
(column depths are [10, 5])
[1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 7, 7, 9] => 13
(column depths are [13, 5])
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9] => 13
(column depths are [13, 5])
[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9] => 21
(column depths are [21, 12, 3])
Это код-гольф, поэтому выигрывает самый короткий вход.
Бонусная головоломка
Можете ли вы доказать (или опровергнуть), что стратегия, описанная в разделе «Цифры используют следующую стратегию для копания», всегда дает максимально глубокое подземелье для данных цифр?
источник