Задача с простыми правилами, но нетривиальными алгоритмами. :-)

задача

Возьмите ввод в виде разделенных пробелом целых чисел:

N A B S

Где N - длина стороны двумерной квадратной матрицы, заполненной уникальными числами (целыми числами) между A и B включительно. Для каждой строки и столбца в этой матрице сумма всегда одна и та же: S. (Другими словами, матрица представляет собой полумагический квадрат).

Заметка:

Все цифры положительные. Исключение составляет А, которое может быть 0.

Примеры

Для

3 1 10000 2015

правильное решение будет

Для

8 1 300 500

правильное решение будет

Выход

Ваш вывод должен быть таблицей ASCII. Пример для первого примера выше:

 384  159 1472
1174  499  342
 457 1357  201

Выровненные вправо целые числа, дополненные пробелами. Ширина каждого столбца - это ширина наибольшего целого числа в этом столбце.

счет

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

CJam, 119 91 байт

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?

Это доказуемо правильный, недетерминированный подход.

На моем рабочем столе второй тестовый пример обычно заканчивается менее чем за 10 минут.

Первый случай заканчивается мгновенно. Попробуйте онлайн в интерпретаторе CJam .

Пробный прогон

$ cjam grid.cjam <<< '8 1 300 500'
77  66  37 47  56  46 86  85
63 102  70 72  49  54 81   9
62  69  58 57  71  17 48 118
64  65  67 87  53  44 80  40
73  60  55 89  51  76 84  12
68  59  28 78  74  38 50 105
61  75  52 43 125  83 42  19
32   4 133 27  21 142 29 112

идея

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

• Вместо псевдослучайного генерирования квадрата длины стороны N , мы генерируем квадраты длины стороны N-1 , добавляем один столбец, чтобы сформировать прямоугольник N × (N-1) , строки которого имеют сумму S , затем одну строку, чтобы сформировать квадрат длина стороны Н , столбцы которой есть сумма S .

  Так как сумма элементов всех столбцов будет NS и сумма элементов первых N-1 строк (N-1) S , последняя строка будет также иметь сумму S .

  Однако этот процесс может генерировать недопустимую матрицу, поскольку нет гарантии, что все элементы последней строки и столбца будут уникальными или попадут в диапазон [A ... B] .

• Выбор квадрата уникальных целых чисел в [A ... B] и длины стороны N-1 равномерно случайным образом занял бы слишком много времени. Мы как-то должны расставить приоритеты для квадратов, которые имеют более высокий шанс получить действительный квадрат с длиной стороны N после применения процесса, описанного в предыдущем пункте.

  Принимая во внимание , что каждая строка и столбец должен иметь сумму S , его элементы имеют в среднем S / N . Таким образом, выбор большего количества элементов, близких к этому среднему, должен увеличить наши шансы.

  Для каждого I в [A ... B] мы псевдослучайно выбираем число с плавающей точкой между 0 и (I - S / N) ² + 1 и сортируем элементы [A ... B] по выбранным числам с плавающей точкой. Мы сохраняем первые N ² числа и помещаем их в порядке чтения в квадрат.

  Предполагая, что на каждом шаге абсолютно равномерное распределение всех действительных чисел между 0 и (I - S / N) ² + 1 , все квадраты имеют ненулевую вероятность выбора, что означает, что процесс в конечном итоге завершится.

Код

q~          e# Read all input from STDIN and evaluate it.
:M;         e# Save "S" in M and discard it from the stack.
),>:R;      e# Transform "A B" into [A ... B], save in R and discard.
(:L         e# Save "N - 1" in L and keep it on the stack.
{           e# If L is non-zero:
  {         e#   Do:
    R{      e#     For each I in R:
      ML)d/ e#       Compute M/Double(L+1).
      -Y#   e#       Subtract the result from I and square the difference.
      )mr   e#       Add 1 and pick a non-negative Double below the result.
    }$      e#     Sort the values of I according to the picks.
    L/      e#     Split the shuffled R into chunks of length L.
    L<      e#     Keep only the first L chunks.
    2{      e#     Do twice:
      {     e#       For each row of the  L x L array.
        M1$ e#       Push M and a copy of the row.
        :+- e#       Add the integers of the row and subtract their sum from M.
        +   e#       Append the difference to the row.
      }%    e#
      z     e#       Transpose rows and columns.
    }*      e#
    :U:+    e#     Save the result in U and concatenate its rows.
    __O|    e#     Push two copies. Deduplicate the second copy.
    =R*     e#     Push R if all elements are unique, an empty array otherwise.
    -       e#     Remove the result's elements from U's elements.
  }g        e#   If the resulting array is non-empty, repeat the loop.
  U{        e#   For each row in U:
    :s      e#     Convert its integers into strings.
    _:,     e#     Copy and replace each string with its length.
    :e>     e#     Compute the maximum length.
    f{      e#     For each integer, push the maximum length; then
      Se[   e#       Left-pad the integer with spaces to that length.
    }       e#
  }%        e#
  z         e#   Transpose rows with columns.
  Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.