Sebuah jumlah surat suara , yang akan kita label B , adalah sejumlah cara mengatur angka dari 1 sampai B (B + 1) / 2 menjadi segitiga, sehingga setiap baris dan kolom dalam urutan meningkat. Empat nomor surat suara pertama adalah:

a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2

a(3)adalah 2, yang berarti ada 2 cara mengatur angka-angka dari 1 hingga 3(3+1)/2 = 6sedemikian segitiga:

1          1
2 3    or  2 4
4 5 6      3 5 6

Lihat entri urutan OEIS untuk lebih jelasnya.

Tantangan Anda, mengingat segitiga surat suara, adalah untuk memverifikasi kebenarannya. Jika memenuhi persyaratan segitiga surat suara (baris dan kolom bertambah), Anda harus menampilkan berapa banyak cara lain (tidak termasuk yang ada di input) yang ada untuk mengatur segitiga dengan benar. Jika segitiga input tidak dibangun dengan benar, Anda seharusnya tidak menghasilkan apa-apa.

Trailing newlines diizinkan.

Memasukkan

Segitiga angka, yang mungkin atau mungkin bukan, merupakan surat suara yang sah. Sebagai contoh:

1
2 3
4 5 6

1
10 5 
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21

Keluaran

Jika inputnya adalah segitiga surat suara yang valid, sisa jumlah cara untuk mengatur angka yang sama dalam segitiga surat suara yang valid. Jika inputnya bukan segitiga surat suara yang valid, tidak ada. Misalnya, input di atas menghasilkan output ini ( <nothing>adalah pengganti untuk output kosong aktual):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Mencetak gol

Ini adalah kode-golf : seperti biasa, byte-count terendah akan menang. Tiebreaker diposting paling awal.

Jelly , 20 byte

;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’

Untuk segitiga pemungutan suara yang valid, waktu lari dan penggunaan memori setidaknya O (n!) , Di mana n adalah jumlah entri dari segitiga. Yang tidak valid dikenali karena terhenti, sehingga tidak mencetak apa pun.

Cobalah online!

Uji coba

Secara lokal, saya dapat memverifikasi bahwa (4) dihitung dengan benar.

$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11

real    6m9.829s
user    6m7.930s
sys     0m2.579s

Bagaimana itu bekerja

;Zµ⁼Ṣ€         Helper link. Argument: T (triangular array)

 Z             Zip/transpose T.
;              Concatenate the original and the transposed copy.
  µ            Begin a new monadic chain, with the previous result (R) as argument.
    Ṣ€         Sort each array in R.
   ⁼           Test for equality with R.
               This returns 1 if T is a ballot triangle, 0 if not.

ẋÇFŒ!ṁ€⁸ÇÐfL’  Main link. Argument: A (triangular array)

 Ç             Call the helper link with argument A.
ẋ              Repeat A that many times.
               This yields an empty array if A is not a ballot triangle.
  F            Flatten the result.
   Œ!          Generate all permutations of the digits of A.
     ṁ€⁸       Mold each permutation like A, i.e., give it triangular form.
               This crashes if permutation array is empty.
        ÇÐf    Filter; keep permutations for which the helper link returns 1.
           L’  Compute the length and decrement it.

Brachylog , 44 byte

{:{o?}a,?z:2a},?ly+yb:3flw
p~c.:laBtybB,.:1&

Cobalah online!

Ini berjalan dalam waktu eksponensial ganda, jadi untuk testcas yang benar, Anda perlu percaya bahwa itu secara teoritis menghasilkan hasil yang benar, untuk segitiga dengan panjang lebih besar dari atau sama dengan 3.

Anda masih dapat menguji testis palsu, yang seharusnya berakhir lebih cepat.

JavaScript (ES6), 143 byte

a=>a.some((b,i)=>b.some((c,j)=>c<b[j-1]||i&&c<a[i-1][j]))?'':(f=n=>n<2||n*f(n-1),g=(n,m=f(n*n+n>>1))=>n<2?m:g(--n,m*f(n)/f(n+n+1)),g(a.length))

Mencari segitiga untuk entri yang tidak valid dan kemudian menggunakan formulasi rekursif rumus di OEIS untuk menghitung hasilnya.