Edycja: Na końcu pytania przyznam nagrodę za 100 punktów reputacji za pierwsze rozwiązanie układanki bonusowej !
Dodam nagrodę do pytania tylko wtedy, gdy pojawi się odpowiedź, ponieważ ta nagroda nie ma terminu.
Biorąc pod uwagę nie malejącą listę jednocyfrowych liczb całkowitych dodatnich, powinieneś określić, jak głębokie lochy będą kopać cyfry.
███ ███ A dungeon with 5 blocks removed and a depth of 3.
███ ███
███ ████
████████
Przed rozpoczęciem kopania ziemia jest pozioma.
Każda cyfra może usunąć dokładnie jeden blok ziemi spod siebie, ale musi osiągnąć tę pozycję spoza lochu, a po usunięciu blok musi opuścić loch. Czyniąc to, cyfra nie może zejść ani podnieść się bardziej niż jej wartość liczbowa na żadnym poziomym kroku.
Cyfry używają następującej strategii do kopania:
- Cyfra o najmniejszej wartości kopie jako pierwsza, a następnie następna koparka jest zawsze następną najmniejszą wartością spośród pozostałych cyfr.
- Pierwsza cyfra może kopać w dowolnej pozycji. (Cały grunt jest taki sam.)
- Następujące cyfry zawsze kopią w najbardziej rozpoczętej w lewo kolumnie, do której można przejść i wyjść. Jeśli taka kolumna nie istnieje, zaczynają kopać nową kolumnę po prawej stronie skrajnej prawej.
Na przykład cyfry 1 1 1 2 3 3
wykopaliby następujący loch (wizualizacja krok po kroku z liczbami oznaczającymi, który rodzaj cyfry wykopuje tę pozycję):
███1████ ███11███ ███11███ ███11███ ███11███ ███11███
████████ ████████ ███1████ ███1████ ███1████ ███13███
████████ ████████ ████████ ███2████ ███2████ ███2████
████████ ████████ ████████ ████████ ███3████ ███3████
████████ ████████ ████████ ████████ ████████ ████████
Objaśnienie dla przykładu:
- Drugi
1
nie mógł wydostać się z jedynej dostępnej kolumny, jeśli pogłębiłby ją do2
głębokości, więc kopałby wprost do niej. - Trzeci
1
może kopać w2
skrajnej lewej kolumnie, tworząc kolumnę -głębną, ponieważ może przenieść się do1
kolumny -głębnej, a następnie na poziom gruntu. - Następny
2
i3
oba mogą kopać w lewej kolumnie. - Ostatni
3
nie może kopać w lewej kolumnie, ale może w następnej.
Wejście
- Nie malejąca lista dodatnich jednocyfrowych liczb całkowitych z co najmniej jednym elementem.
Wynik
- Pojedyncza dodatnia liczba całkowita, głębokość zbudowanego lochu.
Przykłady
Wejście => Dane wyjściowe (z głębokością kolumn lochu od lewej do prawej jako wyjaśnienie, które nie jest częścią wyniku)
[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])
To jest golf golfowy, więc wygrywa najkrótszy wpis.
Układanka premiowa
Czy możesz udowodnić (lub obalić), że strategia opisana w sekcji „Cyfry używają następującej strategii do kopania” zawsze zapewnia najgłębsze możliwe lochy dla danych cyfr?
źródło