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

Pyth, 31 bajtów

Le+bSyMsm,sMJ.T,_<bd>bdm*FkJtUb

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.

C #, 275 272 bajtów

Jest to po prostu funkcja rekurencyjna, która przegląda każdą gałąź i zwraca najlepszy wynik.

Wcięte dla jasności:

using M=System.Math;
int F(int[]n){
    int b=0,g,h,i=0,j,k,l=n.Length;
    if(l<2)
        return n[0];
    for(;++i<l;){
        int[]m=new int[k=M.Max(i,l-i)],o=new int[k];
        for(j=0;j<k;j++){
            m[j]=((g=i-j-1)<0?0:n[g])+((h=i+j)<l?n[h]:0);
            o[j]=h<l&g>=0?n[g]*n[h]:m[j];
        }
        b=M.Max(b,M.Max(F(m),F(o)));
    }
    return b;
}