Wprowadzenie
Po długiej bitwie udało ci się pokonać Sfinksa w konkursie zagadek. Sfinks, pod wrażeniem twoich umiejętności, pragnie dać ci nagrodę współmierną z twoją sprytem i wyczarowuje istnienie paska magicznego pergaminu podzielonego na osiem pól, z których każde zawiera cyfrę.
„Zagnij pergamin”, mówi Sfinks, „tak, że pudełka zachodzą na siebie, a te pola łączą się poprzez dodawanie lub mnożenie. Kiedy jedno pudełko pozostanie, jego wartość będzie twoją nagrodą w złotych monetach”.
Zadanie
Musisz napisać program lub funkcję, która pobiera jako dane wejściowe listę / tablicę / cokolwiek z ośmiu liczb naturalnych i zwraca / drukuje maksymalną możliwą nagrodę, jaką można uzyskać poprzez serię operacji „bigowania”.
Mechanika
Operacja „bigowania” jest wykonywana na pewnej liczbie komórek i za pomocą operatora +
lub *
operatora. Pierwsze n komórek listy jest zwijane i łączone z komórkami docelowymi za pomocą operatora. Wszelkie komórki, które nie zostaną wykorzystane w operacji scalania, pozostaną niezmodyfikowane.
Oto przykład bigowania przy użyciu n = 3 komórek:
za pomocą jednego z dodatków, co spowodowałoby to:
lub pomnożenie, które spowodowałoby to:
Uwaga: Dla uproszczenia marszczenie z mniej niż 1 komórką jest niedozwolone, podobnie jak marszczenie z liczbą komórek większą lub równą długości listy. Listę można jednak zwiększyć o ponad połowę liczby komórek.
Lista 8 komórek może być pomarszczona o 5, w wyniku czego powstanie nowa lista o długości 5:
[0,1,2,3,4,5,6,7]
pomniejszona o 5 komórek za pomocą +
operatora dałaby [9,9,9,1,0]
.
Punktacja
Standardowy kod golfowy - kod, który generuje prawidłowe dane wyjściowe i ma najmniejszą liczbę bajtów wygrywa.
Premia: Jeśli kod również zwraca / drukuje sekwencję operacji bigowania, która prowadzi do maksymalnej nagrody, pomnóż swój wynik przez 0,8. Przykładowe dane wyjściowe mogą wyglądać następująco:
crease 5 +
crease 2 *
crease 2 +
crease 1 *
Przykłady
Przetestuj swój kod, używając tych danych wejściowych i wyników, w postaci 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
Odpowiedzi:
Pyth, 31 bajtów
Definiuje funkcję
y
, która oblicza wartość zagięcia.Demonstracja.
Wykorzystuje to metodę rekultywacyjną, biorąc maksymalną liczbę punktów za każdego możliwego następcę.
Podstawowy przypadek rekurencji jest implementowany przez połączenie danych wejściowych z posortowanymi wartościami możliwych następców, a następnie zabranie końca wynikowej listy. Jeśli na wejściu znajduje się tylko 1 element, nie ma następców, a zatem koniec listy jest jednym z elementów na wejściu.
źródło
C #,
275272 bajtówJest to po prostu funkcja rekurencyjna, która przegląda każdą gałąź i zwraca najlepszy wynik.
Wcięte dla jasności:
źródło