0
0 комментариев

В замке Снежной королевы Кай выращивает льдинки на клетчатом поле, содержащем 100 строк и 100 столбцов. В первый день эксперимента Кай положил маленький кусочек льда высотой 1 в начальную клетку на пересечении первой строки и первого столбца. На второй день ледяной кристалл начал увеличиваться и прорастать на соседних клетках.

 

Рост кристалла в каждый из дней подчиняется следующим правилам:

 

если в клетке уже есть кристалл, то он увеличивается на высоту, равную количеству соседних клеток с кристаллами;

если в клетке ещё не пророс кристалл, то он сразу там появляется. Высота появившегося кристалла в этой клетке равна количеству соседних по сторонам клеток, в которых находятся кристаллы.

Кристаллы очень хрупкие, и могут сломаться под собственным весом. Если в какой-то момент высота кристалла в клетке, расположенной на пересечении строки X и столбца Y, превысит H, то весь кристалл сломается.

 

Кай внимательно следит за экспериментом и хочет знать номер дня, когда льдинка сломается.

 

Пример

В первый день Кай поставил кристалл на поле в начальную клетку. Он знает, что кристалл сломается, если в клетке на пересечении третьей строки и третьего столбца высота кристалла превысит 1. Рассмотрим рисунок.

Открыть изображение в новой вкладке

 

В первый день у начальной клетки не было «соседок» с кристаллами, поэтому во второй день кристалл в начальной клетке не увеличился по высоте. Зато в клетках, соседних с начальной, появились кристаллы высотой 1. Рост кристалла продолжался в 3, 4 и 5 дни. В пятый день в клетке ячейке на пересечении третьей строки и третьего столбца появился кристалл высотой 2. Поэтому в этот день весь кристалл сломался. Ответ для примера — 5.

Кай провёл серию экспериментов с различными ледяными кристаллами. Укажите ответы для каждого из них.

 

В первом эксперименте кристалл разрушается, если его высота в ячейке на пересечении первой строки и первого столбца превысит 21.

 

Число

Во втором эксперименте кристалл разрушается, если его высота в ячейке на пересечении 15-й строки и 1-го столбца превысит 31.

 

Число

В третьем эксперименте кристалл разрушается, если его высота в ячейке на пересечении 50-й строки и 50-го столбца превысит 10.

Arnfinn пометил как избранный вопрос 24.10.2023