Какой алгоритм использовать в этой задаче?

Question

[Oleg Wock]

Сегодня на олимпиаде была задача. Я ее успешно завалил, но до сих пор интересно как ее решать. Вот сама задача:
Есть числовые значения n, k, s.
n = 2..64
2 <= k <= n
s = 1..k^2
Нужно создать матрицу n*n элементов и расположить ноли и единицы так, что бы в любом квадрате размера k*k было ровно s единиц.

Единственным моим предположением было написать функцию, которая проверяет, соответствует ли масив правилам (что я и сделал) и потом прогнать через нее все возможные варианты, но я понимаю что это не эффективно. Да и у меня не получилось получить все варианты массива.

Answer 1

[Oleg Wock]

Пока ждал, нагуглил сам.
Это задача на идею. Когда ее знаешь, то решение кажется очевидным. Однако придумать такое
решение самому иногда (а точнее даже очень часто) не так-то просто. Раскроем секрет задачи:
достаточно сгенерировать любой квадрат K*K, содержащий ровно S единиц, а затем просто заполнить
им квадрат N*N.

Подробнее (+ код на паскале): тыц

Answer 2

[di23]

Ну уже вы сами нашли ответ. Однако если вам хочется что-бы "узор" из единиц и нулей не повторялся примитивно, как в вашем решении, то стоит делать следующим образом:
1. Создать пустую матрицу n*n.
2. В начале координат заполнить рандомно квадрат k*k единицами в кол-ве S.
3. Сместить квадрат k*k на одну клетку.
4. Проверить кол-во единиц в квадрате.
5. Добавить необходимое кол-во единиц в новые клетки, так что бы их было S. Опять же распределив их рандомно.
6. Повторять пункты 3-5 пока матрица n*n не закончится.
7. Профит!!!
Таким образом получаем матрицу n*n с уникальным и не повторяющимся рисунком.

Comments

[nirvimel]

Контрпример: n = 3; k = 2; S = 1; Проход слева направо, сверху вниз.
Шаг 1: рандомно заполняем окно в левом верхнем углу.

100
000
000

Шаг 2: рандомно корректируем окно в правом верхнем углу.

100
001
000

Шаг 3: рандомно корректируем окно в левом нижнем углу.

100
001
010

Шаг 4: что делать с окном в правом нижнем углу?

Answer 3

[Николай]

А почему бы просто не начать заполнять с левого верхнего угла? Ну то есть в первом квадрате проставляем рандомно, а дальше ставим. Куда бы мы не сместились ( вниз или вправо на ряд) - попасть в безвыходную ситуацию мы не можем, а значит и проблем возникнуть не может. Для ускорения стоит использовать вычисления на предыдущих шагах.

Comments

[nirvimel]

Контрпример к такому алгоритму я дал в комментарии к ответу di23