Задача:
Арсений играет в игру «Раскраска». Мальчик выбирает на белой клетчатой доске, имеющей n строк и m столбцов, начальную клетку и красит её в чёрный цвет, после чего происходит несколько ходов. За первый ход все непосредственные соседи выбранной клетки (то есть клетки, имеющие с выбранной общую границу) будут окрашены в чёрный цвет. За второй ход все соседи клеток, окрашенных на предыдущем ходу, тоже окажутся окрашены в чёрный цвет и так далее. Арсений хочет выбрать начальную клетку таким образом, чтобы таблица окрасилась полностью через как можно меньшее число ходов. Через сколько ходов таблица будет окрашена при значении m=125, n=125
Ответ:
Если Арсений начинает с центральной клетки, то вся доска будет закрашена быстрее, так как раскраска будет идти одновременно во всех направлениях от центра.
Рассмотрим случай для доски размером 125×125.
- Первый ход: красим центральную клетку. Размер закрашенного области: 1×1.
- Второй ход: красим все соседние клетки вокруг центральной. Размер закрашенного области: 3×3.
- Третий ход: красим все соседние клетки вокруг 3×3 области. Размер закрашенного области: 5×5.
- И так далее. С каждым ходом размер закрашенного области увеличивается на 2 в каждом измерении.
Следовательно, чтобы покрасить всю доску размером 125×125, нам понадобится: (125-1)/2 + 1 = 63 хода.
Ответ: 63 хода.