Число бюллетеней , который мы будем маркировать B , является количество способов организации числа от 1 до В (В + 1) / 2 в треугольник, таким образом, что каждая строка и столбец в любом порядке возрастания. Первые четыре номера бюллетеня:

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

a(3)это 2, что означает, что есть 2 способа расположить числа от 1 до 3(3+1)/2 = 6такого треугольника:

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

См. Запись последовательности OEIS для более подробной информации.

Ваша задача, учитывая треугольник для голосования, состоит в том, чтобы проверить его правильность. Если он удовлетворяет условиям треугольника голосования (увеличение количества строк и столбцов), вы должны вывести, сколько других способов (кроме одного во входных данных) существует, чтобы правильно расположить треугольник. Если входной треугольник построен неправильно, вы ничего не должны выводить.

Конечные переводы строки разрешены.

вход

Треугольник чисел, который может быть или не быть действительным треугольником голосования. Например:

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

Выход

Если вход является допустимым треугольником голосования, оставшееся количество способов расположить одинаковые числа в действительном треугольнике голосования. Если ввод не является допустимым треугольником голосования, ничего. Например, приведенные выше входные данные генерируют эти выходные данные ( <nothing>является заполнителем для фактического пустого выходного сигнала):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

счет

Это код-гольф : как обычно, выигрывает наименьшее количество байтов. Tiebreaker опубликован раньше всего.

Желе , 20 байт

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

Для допустимых треугольников голосования время выполнения и использование памяти должны быть не менее O (n!) , Где n - количество записей треугольника. Неверные распознаются при сбое, поэтому ничего не печатается.

Попробуйте онлайн!

Тестовый забег

Локально я смог убедиться, что (4) вычислено правильно.

$ 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

Как это устроено

;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.

Брахилог , 44 байта

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

Попробуйте онлайн!

Это выполняется за двойное экспоненциальное время, поэтому для истинных тестовых случаев вы должны поверить мне, что теоретически это дает правильный результат для треугольников с длиной, большей или равной 3.

Вы все еще можете проверить на фальшивые тесты, которые должны закончиться довольно быстро.

JavaScript (ES6), 143 байта

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))

Ищет в треугольнике неверную запись, а затем использует рекурсивную формулировку формулы в OEIS для вычисления результата.