Предлагаю вам сыграть в игру. Я даю вам квадратную сетку, на которой некоторые клетки закрашены, а некоторые могут остаться пустыми. Мы назовём её «шаблоном». Например, сетка может быть одним из таких шаблонов:


У вас есть стопка прозрачных пластмассовых листов, по размеру и форме совпадающих с сеткой, на которые нанесены узоры из чёрных точек:


Стоит заметить, что в каждом из этих узоров ровно по три точки, по одной точке в каждой строке и столбце. Шесть показанных комбинаций — это единственные сетки 3x3, обладающие таким свойством.

Ваша задача — собрать подмножество из прозрачных листов и наложить их на шаблон так, чтобы точки закрывали все закрашенные квадраты, но не попадали ни в один из пустых. Вы можете накладывать на любой из закрашенных квадратов несколько точек, но в целом нужно стремиться использовать как можно меньше листов. Чтобы было интереснее, я предлагаю сделать ставки: за правильное покрытие шаблона 3x3 я плачу 3 доллара, но вы должны мне заплатить по 1 доллару за каждый использованный лист. Выгодная ли это для вас ставка?
Читать дальше ->

https://habrahabr.ru/post/350210/