Wprowadzenie

„Muhuhuhahahah!” Szalony naukowiec się śmieje. „Jesteś uwięziony w mojej małej grze!”

Przed tobą jest śmiertelna jama węży, a za tobą przepaść bez dna. Nie ma wyjścia, utknąłeś!

„Dwa kroki przed tobą to dół węża, a dwa kroki za tobą to przepaść. Ale! Zanim się ruszysz, MUSISZ zapisać sekwencję kroków, do przodu i do tyłu, i daj mi je. Ale! Ponieważ ja czuję się dzisiaj trochę zły , mogę zmusić cię do podjęcia, zamiast każdego kroku, każdego nkroku, gdzie ndługość jest mniejsza niż długość sekwencji!

Wybierz mądrze teraz. ”

Jaka jest maksymalna liczba kroków, które możesz wykonać przed swoją nieuchronną śmiercią?

Zadanie

Powyższe intro jest zwrotem przypuszczenia Erdősa , które niedawno okazało się prawdą (jeśli chcesz dowiedzieć się więcej na ten temat, przejdź do tego filmu , autorstwa Jamesa Grime'a - „ukradłem” mu pytanie o zwrot akcji).

Odpowiedź na wprowadzenie to 11kroki, ale nie będę zagłębiał się w dowody. Odpowiedź, jeśli odległość między tobą a dwoma „niebezpieczeństwami” to 3kroki, to 1160kroki, chociaż nie jest to jeszcze odpowiednio potwierdzone.

Twoim zadaniem jest stworzenie programu, który generuje najdłuższą sekwencję kroków, którą możesz wykonać dla większego x, gdzie xjest liczba kroków między tobą a dwoma „niebezpieczeństwami”. Twój program musi pobrać dane wejściowe xi wygenerować prawidłową sekwencję x.

Na potrzeby tego wyzwania +stanowi krok naprzód i -krok wstecz.

Zatem dane wyjściowe dla danych wejściowych 2to:

+--+-++--++

Który działa, bez względu na to, co nwybierze szalony naukowiec. Dla naszego prowokacji x = 5.

UWAGA: To wyzwanie nie jest duplikatem tego lub tego wyzwania , ponieważ moje wyzwanie koncentruje się na wynikach, w przeciwieństwie do samego kodu - innymi słowy, nie jest to wyzwanie związane z golfem. Poza tym wyzwania te są oparte na tych x = 3, które mają już ustaloną górną granicę.

Zasady:

• Cały program powinien pasować do Twojej odpowiedzi. Jeśli jednak nie pasuje, podaj dodatkowe repozytorium Github lub coś podobnego.
• Możesz zaktualizować zarówno swoją odpowiedź, jak i swój program, jeśli możesz uzyskać lepszy wynik poprzez optymalizację kodu - ale robiąc to, musisz zaktualizować wszystko z poniższej listy.
• W swojej odpowiedzi musisz mieć:
  • Twój program w całości lub link do repozytorium GH hostującego Twój kod
  • Liczba wygenerowanych kroków - będzie to Twój końcowy wynik .
    • Musisz także podać wersję online sekwencji w Pastebin lub coś podobnego. Dzięki temu możemy sprawdzić twoją odpowiedź.
  • Czas ostatniej aktualizacji twojego wyniku, więc nie muszę sprawdzać twojej historii
• NIE wolno wcześniej kodować sekwencji.
• Twój program musi działać dla wszystkichx (gdzie xjest liczba kroków między tobą a otchłanią i otchłanią), ale musisz tylko podać wynik x = 5.

Odpowiedź z największym wynikiem wygrywa!

Rdza, wynik = 4997216, czas = 2017-07-12 00:18 UTC

Poprawia to najlepszy wynik, jaki udało mi się znaleźć w literaturze, która wynosiła 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, On the Erdős Discrepancy Problem , 2014), współczynnik 4,3.

Sekwencja wyjściowa o długości 4997216

Kod źródłowy na GitHub

Bieganie

Program przyjmuje maksymalną rozbieżność jako argument (jest to x -1 w języku wyzwania, aby dostosować się do bardziej powszechnej konwencji matematycznej). Tworzy przyrostowe dane wyjściowe w lekko skompresowanym formacie, który wygląda tak dla x = 3:

$ cargo run --release 2
add +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-+
length 90
delete 12
add --++--+-++-++--+-++--+--+-++--+-
length 110
delete 4
add +-+--+-++-++--+-++--+--+-++-++--+-++-+
length 144
delete 6
add --++-++--+-++--+--++++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-+-
length 214
delete 208
add --+++--+++--+-+--+++--+-+--+++--++---+-+--+-+-++-+--+++--+++--+---++-+--+-++-+++---++--+-++-++--++--+--++--+++--+-+-++-+--+-+--+++---+++-+----+++--+-++--++-+-++--+-+--+-+-++-+--+++--++--+--+--+-++-++---++-++-++-+--+-++
length 224
delete 2
add -+++--+-+--+++---++--+--
length 246
done

gdzie addoznacza dołączenie sekwencji znaków na końcu bieżącej sekwencji, deleteoznacza usunięcie pewnej liczby znaków z końca bieżącej sekwencji i lengthzapewnia długość bieżącej sekwencji. W tym schemacie unika się wytwarzania wielu gigabajtów wyników pośrednich w miarę odkrywania coraz dłuższych sekwencji. Najlepszy wynik można wyodrębnić za pomocą następującego programu w języku Python:

import sys
s = ''
for line in sys.stdin:
    cmd = line.split()
    if cmd[0] == 'delete': s = s[:-int(cmd[1])]
    elif cmd[0] == 'add': s += cmd[1]
    elif cmd[0] == 'length': assert len(s) == int(cmd[1])
print(s)

Jak to działa

Jest tu około tysiąca wierszy kodu, więc będzie to tylko bardzo ogólny przegląd.

Ograniczamy wyszukiwanie do sekwencji całkowicie multiplikatywnych (te z f ( a · b ) = f ( a ) · f ( b )), ponieważ oznacza to, że potrzebujemy jedynie skupić się na ograniczeniu sum częściowych dla n = 1, a częściowych sumy dla n ≥ 2 automatycznie spełnią tę samą granicę.

Dla każdego podłańcucha f ( i + 1),…, f ( j ) częściowo przypisanej sekwencji znaków (więc każdy element to „+”, „-” lub nieznany), zdefiniuj niebezpieczeństwo ₊ ( i , j ), aby było dwa razy liczba „+” minus długość j - i (dla wygody pozwalamy, aby i było tak małe jak - x + 2 i przyjmujemy, że f (- x + 3) = ⋯ = f (0) = „+” dla ten cel). Zdefiniuj niebezpieczeństwo _- ( i , j ) podobnie. Następnie granica sum częściowych dla n= 1 jest równoważne warunkowi, że ilekroć i ≡ j ≡ x (mod 2), niebezpieczeństwo ₊ ( i , j ) ≤ x - 2 i niebezpieczeństwo _- ( i , j ) ≤ x - 2.

Budujemy przyrostową strukturę danych, która obsługuje stałe zapytania czasowe dla podciągów o największym niebezpieczeństwie, z logarytmicznymi aktualizacjami czasu. Działa poprzez powiązanie czterech wartości:

• niebezpieczeństwo ( i , j ),
• max _{i ≤ k ≤ j} niebezpieczeństwo ( i , k ),
• max _{i ≤ k ≤ j} niebezpieczeństwo ( k , j ), i
• max _{i ≤ k ≤ l ≤ j} niebezpieczeństwo ( k , l ),

z każdym łańcuchem o długości 2, co drugim łańcuchem o długości 4, co czwartym łańcuchem o długości 8 i tak dalej. Wartości związane z dłuższym łańcuchem można obliczyć w stałym czasie z wartości powiązanych z jego dwiema połówkami.

Ta struktura, uzupełniona pewnymi informacjami pomocniczymi, pozwala nam bardzo szybko wykonywać propagację ograniczeń i wykrywanie konfliktów na częściowych sekwencjach. Używamy go do wyszukiwania podobnego do CDCL , z propagacją jednostek, poziomami decyzji i niechronologicznym cofaniem (na razie bez uczenia klauzul), w celu uzyskania pełnych sekwencji o coraz większej długości.

Na każdym etapie wyszukiwania zgadujemy najwcześniejszy nieprzypisany znak. Heurystyka zastosowana do tego przypuszczenia jest bardzo ważna dla uniknięcia wielu cofnięć; używamy f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.

Wyniki

Rozbieżności wyszukiwania 0, 1 i 2 natychmiast znajdują optymalne, całkowicie multiplikatywne sekwencje o długości 0, 9 i 246.

Wyszukiwanie rozbieżności 3 blokuje się w ciągu kilku sekund w 41319, co jest dość dalekie od znanej optymalnej całkowicie multiplikatywnej sekwencji o długości 127645 znalezionej przez Le Bras i in., 2014 (i bardzo nieznacznie dłuższego niemultiplikatywnego rozszerzenia długości 130000 znalezionego wkrótce potem ), ale znacznie lepiej niż najlepiej znana sekwencja przed sekwencją o długości 17000 .

Wyszukiwanie rozbieżności 4 poprawia najdłuższą sekwencję mniej więcej nieprzerwanie przez około pięć minut, aż utknie na 4997216. Najlepsza wcześniej znana sekwencja o długości 1148805 = 9 · 127645 została rozwinięta z sekwencji rozbieżności 3 poprzez zastąpienie każdego znaku s znakiem + - - + - ++ - s . O ile wiem, tak długie sekwencje są zbyt trudne, aby ogólny solver SAT mógł je bezpośrednio poprawić (ale może ty, drogi czytelniku, możesz udowodnić, że się mylę!).

Spodziewam się, że będę musiał dodać do mojego programu klauzulę dotyczącą uczenia się, aby pokonać te bariery.

Sekwencja jako mapa bitowa 2187 × 2285

(Kliknij, aby wyświetlić w pełnej rozdzielczości.)

Haskell , wynik = 9020, czas = 2017-06-09 00:52 UTC

f 1=""
f n="+-"++do c<-f(n-1)++"-";"-+-++-"++c:"+-"

Wypróbuj online!

To wyniki (9 ^{n - 1} - 1) ⋅11 / 8 dla wszystkich n . Oto kilka pierwszych wyników:

n=1, length=0: 
n=2, length=11: +--+-++--+-
n=3, length=110: +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+-
n=4, length=1001: +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+-
n=5, length=9020: +--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++-++--+-++-++--+-++--+--+-++--+--+-++-++--+-++--+--+-++--+-