pengantar

"Muhuhuhahahah!" Ilmuwan gila itu tertawa. "Kamu terjebak dalam gim kecilku sendiri!"

Di depan Anda ada lubang ular yang mematikan, sementara di belakang Anda ada jurang tanpa dasar. Tidak ada jalan keluar, Anda terjebak!

"Dua langkah di depan Anda adalah lubang ular, dan dua langkah di belakang Anda adalah jurang. Tapi! Sebelum Anda bergerak, Anda HARUS menuliskan urutan langkah, maju dan mundur, dan berikan kepada saya. Tapi! Karena saya Saya merasa sedikit jahat hari ini, saya bisa membuat Anda mengambil, alih-alih setiap langkah, setiap nlangkah, di mana nkurang dari panjang urutan Anda!

Pilih dengan bijak, sekarang. "

Berapa jumlah maksimum langkah yang dapat Anda ambil sebelum kematian Anda yang akan segera terjadi?

Tugas

Intro di atas adalah twist pada dugaan perbedaan Erd , yang baru-baru ini terbukti benar (jika Anda ingin memahami lebih lanjut tentang ini, buka video ini , oleh James Grime - Saya "mencuri" pertanyaan twist darinya).

Jawaban untuk intro adalah 11langkah - langkah, tetapi saya tidak akan terlalu mendalam dengan bukti. Jawabannya, jika jarak antara Anda dan kedua "bahaya" itu adalah 3langkah, adalah 1160langkah, meskipun itu belum divalidasi dengan benar.

Tugas Anda adalah membuat program yang menghasilkan urutan langkah terpanjang yang dapat Anda capai untuk yang lebih besar x, di mana xjumlah langkah antara Anda dan dua "bahaya". Program Anda harus mengambil input untuk x, dan menampilkan urutan yang valid untuk itu x.

Untuk keperluan tantangan ini, +mewakili langkah maju, dan -mewakili langkah mundur.

Jadi, output untuk input 2adalah:

+--+-++--++

Yang berhasil, apa pun yang ndipilih ilmuwan gila. Untuk tantangan kita x = 5,.

CATATAN: Tantangan ini bukan merupakan duplikat dari tantangan ini atau tantangan ini , karena tantangan saya berfokus pada output, yang bertentangan dengan kode itu sendiri - dengan kata lain, ini bukan tantangan kode golf. Selain itu, tantangan-tantangan ini didasarkan x = 3, yang sudah memiliki batas atas yang mapan.

Aturan:

• Seluruh program Anda harus sesuai dengan jawaban Anda. Namun, jika tidak cocok, berikan repositori Github tambahan, atau yang serupa.
• Anda dapat memperbarui jawaban dan program Anda, jika Anda bisa mendapatkan skor yang lebih baik dengan mengoptimalkan kode Anda - tetapi dengan melakukannya, Anda harus memperbarui semua yang ada dalam daftar di bawah ini.
• Dalam jawaban Anda, Anda harus memiliki:
  • Program Anda, secara keseluruhan, atau tautan ke repositori GH yang menampung kode Anda
  • Jumlah langkah yang dihasilkan - ini akan menjadi skor akhir Anda .
    • Anda juga harus memberikan versi online dari urutan dalam Pastebin, atau yang serupa. Ini agar kami dapat memeriksa jawaban Anda.
  • Waktu skor akhir Anda terakhir diperbarui, jadi saya tidak perlu memeriksa riwayat Anda
• Anda mungkin TIDAK urutan hardcode sebelumnya.
• Program Anda harus bekerja untuk semuax (di mana xjumlah langkah antara Anda dan lubang & jurang), tetapi Anda hanya perlu memberikan skor untuk x = 5.

Jawaban dengan skor terbesar menang!

Karat, skor = 4997216, waktu = 2017-07-12 00:18 UTC

Ini meningkatkan hasil terbaik yang dapat saya temukan dalam literatur, yaitu 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, Pada Masalah Ketimpangan Erd , 2014), dengan faktor 4,3.

Urutan output dengan panjang 4997216

Kode sumber di GitHub

Lari

Program menerima perbedaan maksimum sebagai argumen (ini adalah x - 1 dalam bahasa tantangan, untuk menyelaraskan dengan konvensi matematika yang lebih umum). Ini menghasilkan keluaran tambahan dalam format yang sedikit terkompresi yang terlihat seperti ini untuk 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

di mana addberarti menambahkan urutan tanda ke akhir urutan saat ini, deleteberarti menghilangkan beberapa tanda dari akhir urutan saat ini, dan lengthmenegaskan panjang urutan saat ini. Skema ini menghindari produksi banyak gigabita hasil antara karena urutan yang lebih lama ditemukan. Anda dapat mengekstrak hasil terbaik sejauh ini dengan program Python berikut:

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)

Bagaimana itu bekerja

Ada sekitar seribu baris kode di sini, jadi ini hanya akan menjadi gambaran yang sangat kasar.

Kami membatasi pencarian untuk urutan multiplikasi sepenuhnya (yang dengan f ( a · b ) = f ( a ) · f ( b )), karena itu berarti kita hanya perlu memusatkan perhatian pada diri kita sendiri dengan membatasi jumlah parsial untuk n = 1, dan parsial jumlah untuk n ≥ 2 akan memenuhi batas yang sama secara otomatis.

Untuk setiap substring f ( i + 1), ..., f ( j ) dari urutan tanda yang ditetapkan sebagian (sehingga setiap elemen adalah '+', '-', atau tidak diketahui), tentukan bahaya ₊ ( i , j ) menjadi dua kali lipat jumlah '+' s minus panjang j - i (untuk kenyamanan, kami memungkinkan saya untuk menjadi sekecil - x + 2 dan menganggap f (- x + 3) = ⋯ = f (0) = '+' untuk tujuan ini). Tetapkan bahaya _- ( i , j ) dengan cara yang sama. Kemudian terikat pada jumlah parsial untuk n= 1 setara dengan kondisi bahwa setiap kali saya ≡ j ≡ x (mod 2), bahaya ₊ ( i , j ) ≤ x - 2 dan bahaya _- ( i , j ) ≤ x - 2.

Kami membangun struktur data tambahan yang mendukung kueri waktu konstan untuk substring dengan bahaya terbesar, dengan pembaruan waktu logaritmik. Ia bekerja dengan mengaitkan empat nilai:

• bahaya ( i , j ),
• maks _{i ≤ k ≤ j} bahaya ( i , k ),
• maks _{i ≤ k ≤ j} bahaya ( k , j ), dan
• maks _{i ≤ k ≤ l ≤ j} bahaya ( k , l ),

dengan setiap string dengan panjang 2, setiap string dengan panjang 4, setiap string keempat dengan panjang 8, dan seterusnya. Nilai-nilai yang terkait dengan string yang lebih panjang dapat dihitung dalam waktu konstan dari nilai-nilai yang terkait dengan dua bagiannya.

Struktur ini, ditambah dengan beberapa informasi tambahan, memungkinkan kita melakukan propagasi kendala dan deteksi konflik pada urutan parsial dengan sangat cepat. Kami menggunakannya untuk melakukan pencarian mirip- CDCL , dengan propagasi unit, tingkat keputusan, dan backtracking non-kronologis (tapi tanpa pembelajaran klausa, untuk saat ini), untuk urutan penuh dengan panjang yang lebih panjang dan lebih panjang.

Pada setiap langkah pencarian, kami membuat perkiraan untuk tanda yang belum ditetapkan paling awal. Heuristik yang digunakan untuk menebak ini sangat penting untuk menghindari banyak backtracking; kita menggunakan f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.

Hasil

Perbedaan 0, 1, dan 2 pencarian segera menemukan urutan multiplikasi sepenuhnya optimal panjang 0, 9, dan 246.

Pencarian ketidaksesuaian 3 terhenti dalam hitungan detik pada 41319, yang cukup jauh dari urutan multiplikatif optimal panjang 127645 yang diketahui ditemukan oleh Le Bras et al., 2014 (dan ekstensi non-multiplikatif dengan panjang 130000 yang sedikit lebih lama ditemukan setelah itu ), tetapi jauh lebih baik daripada urutan yang paling dikenal sebelum yang panjangnya 17000 .

Perbedaan 4 pencari meningkatkan urutan terpanjang lebih atau kurang terus-menerus selama sekitar lima menit sampai mendapat terjebak di 4997216. yang terbaik urutan sebelumnya dikenal panjang 1.148.805 = 9 · 127.645 diperluas dari perbedaan 3 urutan dengan mengganti setiap tanda s dengan + - - + - ++ - s . Sejauh yang saya tahu, urutan selama ini terlalu sulit bagi pemecah SAT umum untuk meningkatkan secara langsung (tapi mungkin Anda, pembaca yang budiman, dapat membuktikan saya salah!).

Saya berharap saya perlu menambahkan semacam klausa belajar ke program saya untuk melewati hambatan ini.

Urutan sebagai bitmap 2187 × 2285

(Klik untuk melihat pada resolusi penuh.)

Haskell , skor = 9020, waktu = 2017-06-09 00:52 UTC

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

Cobalah online!

Skor ini (9 ^{n - 1} - 1) ⋅11 / 8 untuk semua n . Berikut adalah beberapa keluaran pertama:

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