10
|
Задача 779. Змейка из клетокпостоянный адрес задачи: http://www.diofant.ru/problem/2411/показать код для вставки на свой сайт >> |
Задачу решили:
45
всего попыток:
76
поделиться задачей:
|
|
|
Задача опубликована:
20.08.12 08:00
Прислал:
georgp
Вес:
1
сложность:
1
класс:
8-10
баллы: 100
Темы:
комбинаторика
|
|
Лучшее решение:
zmerch
|
Рассмотрим одноклеточное существо змейку – фигуру, первоначально содержащую один квадрат и растущую в плоскости за счет прибавления квадратных клеток того же размера к какой-нибудь его стороне. Стороны этой фигуры не должны выходить за пределы квадрата 1999 на 1999. Найти максимальное число клеток, которое может иметь связная фигура (в комбинаторике такая фигура называется полимино). Связность заключается в том, что в ней нет дыр. Кроме того, никакая точка фигуры не может одновременно принадлежать четырем клеткам, а каждая клетка не может иметь только одну точку общую с остальными клетками.
Для иллюстрации приведен рисунок, показывающий процесс роста фигуры и запрещенные позиции, которые не может содержать фигура в процессе своего роста.
ПРОЦЕСС РОСТА ФИГУРЫ
ЗАПРЕЩЕННЫЕ ПОЗИЦИИ
a) b) c)
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
В зависимости от того, что есть дыра (или в каком смысле понимается связность), возникают разные задачи. Ждём разъяснений.
Может быть я что-то не понял, но в данной задаче мне кажется, что условие полностью ясно (да и мой ответ был принят). Как раз приведно 3 примера (a, b, c) чего запрешенно, а остальное разрешенно. Попробуйте придумать фигуру, для которой не понятно из условия, "законная" ли она или нет.
Может быть такая формулировка: А. Из каждой клеточки фигуры можно перейти к любой другой по сторонам квадратиков: вверх, вниз, вправо, влево. Б. Из каждой клеточки (внутри квадрата 1999 на 1999), НЕ ПРИНАДЛЕЖАЩЕЙ фигуре, можно таким же образом "выйти наружу". В. Запреты "b" и "c".
<<Попробуйте придумать фигуру, для которой не понятно из условия, "законная" ли она или нет.>>
Да, существует ПРОЦЕСС РОСТА ФИГУРЫ (змеи) до 21-ой клетки! на квадрате 5*5 - И непонятно: "законная" ли она или нет, поскольку доказательство МАКСИМАЛЬНОСТИ ответа и к этой задаче 5*5, и к данной 779 при АВТОРСКОМ(!) условии оказывается совершенно очевидным!