В замке Снежной королевы Кай выращивает льдинки на клетчатом поле, содержащем 100 строк и 100 столбцов. В первый день эксперимента Кай положил маленький кусочек льда высотой 1 в начальную клетку на пересечении первой строки и первого столбца. На второй день ледяной кристалл начал увеличиваться и прорастать на соседних клетках.
Рост кристалла в каждый из дней подчиняется следующим правилам: если в клетке уже есть кристалл, то он увеличивается на высоту, равную количеству соседних клеток с кристаллами; если в клетке ещё не пророс кристалл, то он сразу там появляется. Высота появившегося кристалла в этой клетке равна количеству соседних по сторонам клеток, в которых находятся кристаллы. Кристаллы очень хрупкие, и могут сломаться под собственным весом. Если в какой-то момент высота кристалла в клетке, расположенной на пересечении строки X и столбца Y, превысит H, то весь кристалл сломается. Кай внимательно следит за экспериментом и хочет знать номер дня, когда льдинка сломается.
В первый день Кай поставил кристалл на поле в начальную клетку. Он знает, что кристалл сломается, если в клетке на пересечении третьей строки и третьего столбца высота кристалла превысит 1.
В первый день у начальной клетки не было «соседок» с кристаллами, поэтому во второй день кристалл в начальной клетке не увеличился по высоте. Зато в клетках, соседних с начальной, появились кристаллы высотой 1. Рост кристалла продолжался в 3, 4 и 5 дни. В пятый день в клетке ячейке на пересечении третьей строки и третьего столбца появился кристалл высотой 2. Поэтому в этот день весь кристалл сломался. Ответ для примера — 5.
Кай провёл серию экспериментов с различными ледяными кристаллами. Укажите ответы для каждого из них.
В первом эксперименте кристалл разрушается, если его высота в ячейке на пересечении первой строки и первого столбца превысит 21.
Во втором эксперименте кристалл разрушается, если его высота в ячейке на пересечении 15-й строки и 1-го столбца превысит 31.
В третьем эксперименте кристалл разрушается, если его высота в ячейке на пересечении 50-й строки и 50-го столбца превысит 10.
1 Ответ
В первом эксперименте кристалл разрушается, если его высота в ячейке на пересечении первой строки и первого столбца превысит 21 — на 12 день.
Во втором эксперименте кристалл разрушается, если его высота в ячейке на пересечении 15-й строки и 1-го столбца превысит 31 — на 25 день.
В третьем эксперименте кристалл разрушается, если его высота в ячейке на пересечении 50-й строки и 50-го столбца превысит 10 — в 4 раза дольше, на 100 день.