Вниз  Задачи и головоломки
- 14.06.2014 / 01:02
Ксакеп
  Модератор форума

Ксакеп 
Сейчас: Offline
В общем, это новая версия старой темы, которая однозначно понравится всем. Здесь желательно выкладывать интересные задачи на собеседованиях, какие-либо задачи по программированию, логике, математике, что-то из головоломок и так далее.

Олимпиадное программирование: http://codeforces.ru/
Прикладная математика/информатика: http://projecteuler.net/
Био-информатика: http://rosalind.info/

Изменено Ксакеп (14.06 / 17:33) (всего 1 раз)
- 14.06.2014 / 01:14
SeTSeR
  Пользователь

SeTSeR 
Сейчас: Offline
Ну, вот простая:
В квадрате 4x4 все клетки, кроме левой верхней(в ней стоит минус), заполнены плюсами. За одну операцию можно поменять все знаки в столбце/строке на противоположные. Можно ли за конечное кол-во операций сделать все знаки плюсами? После ответа на этот вопрос выяснить, при каких положениях это возможно и сколько таких положений вообще. Если сможете сделать и это, то обобщить эту задачу на любые квадраты(кроме 1x1) и не-квадраты.
- 14.06.2014 / 17:36
SeTSeR
  Пользователь

SeTSeR 
Сейчас: Offline
Все прямо-таки бросились решать :gg:

А решение задачи куда писать?
- 14.06.2014 / 17:42
Ксакеп
  Модератор форума

Ксакеп 
Сейчас: Offline
SeTSeR, сюда же под спойлер. Если задача сложная, лучше сразу в одном посте %)
- 14.06.2014 / 17:46
Helltar
  Пользователь

Helltar 
Сейчас: Offline
Никто не хочет ничего решать, все хотят трулялякать. Это печально ._.
- 14.06.2014 / 18:13
SeTSeR
  Пользователь

SeTSeR 
Сейчас: Offline
Ксакеп, а, ну ок, вот решение:
1) Рассмотрим верхний левый квадрат 2x2 и заметим, что если до операции в строке/столбце было x плюсов, то после операции в ней будет 2-x плюсов. Применяя это к первой строке, получаем, что в ней всегда будет 1 минус, т. е. угловой квадрат 2x2 вымостить одними плюсами мы не сможем.
2) Очевидно, что если каждый под-квадрат 2x2 нашего квадрата 4x4 можно вымостить плюсами, то и сам квадрат можно вымостить плюсами. С другой стороны, если можно из положения N привести квадрат в положение 0(без минусов), то, очевидно, можно провести обратное преобразование. От этого и будем отталкиваться при подсчёте. Сначала будем инвертировать только строки. Таким образом получим положений. Каждому из них соответствует положений, в которых инвертированы какие-то столбцы. Всего разрешимых положений.
3) Поступая аналогично предыдущему, получаем формулу , где c - число разрешимых положений, a - сторона квадрата.
Для прямоугольника формула такая: , где a, b - стороны, c - число разрешимых положений.

Изменено SeTSeR (14.06 / 18:14) (всего 1 раз)
Наверх  Всего сообщений: 6
Фильтровать сообщения
Поиск по теме