|
|
 |
Условие
Паутина имеет вид клетчатой сетки 100×100 узлов (другими словами, это сетка 99×99 клеток). В каком-то её углу сидит паук, а в некоторых 100 узлах к паутине приклеились мухи. За ход паук может переместиться в любой соседний с ним узел. Может ли паук гарантированно съесть всех мух, затратив не более
а) 2100 ходов;
б) 2000 ходов?
Решение 1
б) Разделим сетку на 10 горизонтальных полосок по 1000 узлов (9×99 клеток). Пусть паук сидит в левом нижнем углу. Сначала он двигается слева направо по нижнему краю нижней полоски, пока не увидит муху, приклеенную в этой же полоске над ним. Тогда он пересекает полоску по вертикали, съедая муху, и продолжает движение направо по верхнему краю полоски, пока не увидит муху, приклеенную под ним. Тогда он снова переходит на нижний край полоски и т.д. Достигнув правого края полоски он переходит по вертикали на нижний край следующей полоски. Всего на это он затратит не более 99 + 9k + 10 ходов, где k – количество мух в первой полоске. Далее он повторяет "процедуру", двигаясь справа налево вдоль второй полоски и т.д. На уничтожение всех 100 мух ему потребуется не более 10·99 + 9·100 + 9·10 = 1980 ходов.
Решение 2
б) Занумеруем горизонтальные линии, проходящие через узлы, числами от 1 до 100. Покрасим красным цветом линии с номерами 5, 15, ..., 95 (10 линий), а синим – линии с номерами 1, 10, 20, ..., 100 (11 линий). Дополним красные линии (проведя 99 вертикальных единичных отрезков) до красной змейки, а синие линии – до синей змейки (змейка идёт из левого верхнего угла в один из нижних углов). Длина красной змейки – 99·11, а синей – 99·12.
От любой мухи можно дойти как до красной змейки, так и до синей не более чем за пять ходов. Муху, от которой до красной змейки можно дойти за три или менее ходов, назовём красной, в противном случае – синей. От любой синей мухи до синей змейки можно дойти не более чем за один ход.
Если красных мух не меньше 59, то алгоритм такой: паук идёт по красной змейке; как только он доходит до точки, ближайшей к какой-нибудь мухе – отходит к этой мухе, съедает её, возвращается на красную змейку и идёт по ней дальше. Длина пути будет не более 99·11 + 59·6 + 41·10 = 1853 (забирая синюю муху, он тратит не более десяти ходов, забирая красную – не более шести).
Если же красных мух не более 58, то синих мух не менее 42, и тогда алгоритм тот же, только паук идёт по синей змейке. Длина пути не более
99·12 + 42·2 + 58·10 = 1852 (забирая красную муху, он тратит не более десяти ходов, забирая синюю – не более двух).
Ответ
Может.
Замечания
баллы: 5 + 5
