31 дек. 2014 г.

Что хорошо в нынешнем КВН?

Добрый праздничный день!

Год переполнен событиями, среди них есть хорошие, есть перспективные и многообещающие, но хватает и разных — не будем сейчас о них. Давайте лучше чуть-чуть поговорим о веселье и формах расслабления, ведь отдыхать тоже надо.

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

Вот мой набор (в скобках ссылки на некоторые примеры):
1) Фёдор Двинятин (видео),
2) Кефир (видео),
3) Мурманск (видео).

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

Хорошего Нового года! Тёплого общения с близкими! Надеюсь, вы прочитали это сообщение в 2015 году, а ещё лучше — на 2-3 неделе января :) Если будет скучно на длинных выходных, то предлагаю добить задачку «про немагические прямоугольники».

2 дек. 2014 г.

Двоичные немагические прямоугольники

Добрый день.

Начало нового месяца — это часто хороший повод порешать очередную задачку от команды IBM (год назад мы уже обращались к этому источнику). Предлагаю перевод декабрьского задания (или прочтите оригинал):

У двоичной матрицы NxM (т.е. в ячейках которой только нули и единицы) мы можем посчитать N сумм значений в строках и M сумм значений в столбцах. Эти суммы иногда могут однозначно задавать матрицу. Например, суммы [1,2,0][2,1] могут быть только у следующей матрицы:
     1 0
     1 1
     0 0

Но иногда суммы задают не одну матрицу. Например, суммы [1,1,2][2,2] соответствуют следующим двум матрицам:
     0 1     1 0
     1 0     0 1
     1 1     1 1

Декабрьское задание состоит в поиске таких сумм, которые описывают ровно 29 разных двоичных матриц. Чтобы исключить тривиальные решения, наложим ещё одно ограничение: матрица должна содержать не более 50 бит. В качестве решения принимаются две строки: в первой N целых чисел и во второй M целых чисел. Произведение N*M должно быть не больше 50.


Если вам интересен такой класс задачек, то давайте поделимся друг с другом в комментариях ответами на следующие вопросы:
1) Придумали ли вы тривиальное решение (более 50 бит, на которое намекают авторы задачи)?
2) Какие количества двоичных матриц вы умеете выражать преложенным способом (в условии задачи есть решения для 1 и 2, а спрашивается про 29, но ведь есть ещё много других чисел)?
3) Придумали ли вы способы «умножать» ранее найденное решение (т.е. получать наборы сумм, описывающих N*k матриц, имея решение для N матриц)?
4) Нашли ли вы решение для 29 матриц и небольшого их размера? Если да, то можете вписать своё имя на сайт IBM, отправив им своё решение (каждый месяц несколько десятков человек пользуются этой возможностью)

Хорошей недели и интересных задачек!

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний