Ловля крыс

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Ловля крыс

Сообщение Dendr »

Versus писал(а):Для глухой крысы, видимо, придётся разбить всё пространство на блоки, ограниченные радиусом слуха крысы. И простреливать их по очереди в определённом порядке. Но тут надо ещё подумать надо оптимизацией процесса.
Разбивать на блоки - плохо, потому что когда простреливаемый ящик меняется, мы можем захватить ящик из другого блока. Для слышащей на 1 ящик - просто. N-1 выстрела - и готово (даже быстрее, чем для полностью глухой!) А вот при N=2 - где-то в промежутке. Перебор руками тяжелый - вариативность слишком высокая.

Аватара пользователя
Versus
Литератор-любитель
Литератор-любитель
Сообщения: 404
Зарегистрирован: 12 май 2006, 13:36

Re: Ловля крыс

Сообщение Versus »

Про блоки это я погорячился. Очень хотелось свести задачу к уже решённой по пути наименьшего сопротивления.
Dendr писал(а):Для слышащей на 1 ящик - просто. N-1 выстрела - и готово (даже быстрее, чем для полностью глухой!) А вот при N=2 - где-то в промежутке. Перебор руками тяжелый - вариативность слишком высокая.
Что-то меня терзают смутные сомнения насчёт N-1 выстрела. Крыса, как только слышит выстрел в соседнем ящике, либо перебегает в тот ящик, в который мы только что стреляли, либо убегает дальше, загоняя себя в тупик. Значит единственная тактика - это тактика Шшока (дублировать выстрел в каждый ящик), иначе проскочит на уже зачищенную территорию. В результате приходим к тем же 2*(n-2), только с другого боку.

Хочу прояснить пару моментов по терминологии:
"Нечётной" называется движущаяся (то есть, наш следующий выстрел заставит крысу двигаться) крыса, удалённая от точки стрельбы на нечётное число ящиков.
"Чётной" называется движущаяся крыса, удалённая на чётное число ящиков.

При последовательном расстреле ящиков чётность крысы не меняется. Значит, нечётная крыса всегда проскочит под пулей, а чётная будет убита.
Смысл любой тактики двойным выстрелом в один и тот же ящик поменять чётность крысы и пристрелить её. Крыса с радиусом слуха 1 всегда нечётная (либо мёртвая).

Если мы приближаемся последовательно к радиусу слуха крысы, то её чётность будет зависеть от чётности радиуса. При чётном значении радиуса, крыса будет чётной, а при нечётном - нечётной. Соответственно, крысу с чётным радиусом мы всегда убьём за один проход, а нечётная всегда ускользнёт за пределы радиуса, а когда снова попадёт в него, то снова будет нечётной. Поэтому для крысы с нечётным радиусом требуется тактика двойных выстрелов, второй выстрел в дуплете либо убивает крысу, либо меняет её чётность. И стрелять приходится в каждый ящик со второго по предпоследний, так как мы ничего не знаем о первоначальном расположении крысы.

Крысу с чётным радиусом можно было бы убить за один проход, если бы мы точно знали, что она не слышит первого выстрела. Но существует вероятность, что первый выстрел будет внутри радиуса слуха такой крысы. При этом она может сидеть через нечётное число ящиков (и стать нечётной). В таком случае при последовательной стрельбе слева направо крыса либо выйдет за пределы радиуса слуха и автоматически станет чётной позже, либо мы поменяем её чётность, стрельнув дуплетом в предпоследний ящик, и убьём на обратном пути. В любом случае потребуется те же 2*(n-2) выстрелов для гарантированной дератизации ящиков.

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

Аватара пользователя
Slavaa
Писатель на заборах
Писатель на заборах
Сообщения: 119
Зарегистрирован: 29 сен 2008, 18:41
Пол: Мужской
Откуда: С-Петербург

Re: Ловля крыс

Сообщение Slavaa »

Стреляем во вторуую - крыса точно не в первой
Еще раз во вторую - она не в первой и не второй
После двух раз по третьей - и не в третьей
таким образом делаем по 2 выстрела по каждой коробке, кроме первой и последней
итого 1996

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Ловля крыс

Сообщение maksim82 »

Slavaa писал(а):Стреляем во вторуую - крыса точно не в первой
Еще раз во вторую - она не в первой и не второй
После двух раз по третьей - и не в третьей
таким образом делаем по 2 выстрела по каждой коробке, кроме первой и последней
итого 1996
Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Ловля крыс

Сообщение Dendr »

Versus писал(а):Что-то меня терзают смутные сомнения насчёт N-1 выстрела.
Дважды во вторую:
с первого выстрела либо убьем крысу из второго ящика, либо заставим крысу из 1-го перебежать во второй, либо из 3-го в 1-й, либо из 3-го в 4-й. Если рыса в 4-м или дальше, она стоит на месте.
со второго - либо стреляем в пустой, либо убиваем крысу
Результат - крысы точно нет в первых трех ящиках

Дважды в 4-й - аналогично, итого - нет в первых пяти.

И так далее.

Аватара пользователя
Slavaa
Писатель на заборах
Писатель на заборах
Сообщения: 119
Зарегистрирован: 29 сен 2008, 18:41
Пол: Мужской
Откуда: С-Петербург

Re: Ловля крыс

Сообщение Slavaa »

Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.

А откуда она перебежит во вторую???
Если она точно не в перввой, то только из третьей и мы убъем ее когда выстрелим по третьей

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Ловля крыс

Сообщение maksim82 »

Slavaa писал(а):Когда начинаем стрелять по третей, крыса перебегает во 2-ю. После 2-го выстрела по 3-ей она перебегает в 1-ю.

А откуда она перебежит во вторую???
Если она точно не в перввой, то только из третьей и мы убъем ее когда выстрелим по третьей
Каждая итерация состоит из двух событий: выстрел и перемещение крысы.
Итерация 1 (И1). Выстрел во 2 коробку (2К) гарантирует, что в начале И2 К1 будет пуста
Итерация 2. Выстрел снова в К2 нам опять гарантирует пустоту К1, но, поскольку после выстрела следует перемещение крысы, это нам не гарантирует пустоту К2 в начале следующей итерации.

Короче, алгоритм по 2 выстрела подряд в каждую коробку не катит. Думайте дальше.

Аватара пользователя
ХМАО
Писатель на заборах
Писатель на заборах
Сообщения: 154
Зарегистрирован: 24 апр 2009, 21:15
Пол: Мужской
Откуда: ХАНТЫ-МАНСИЙСК

Re: Ловля крыс

Сообщение ХМАО »

Очень внимательно прочитал условия задачи и комментарии к ней.
Вот алгоритм дейсвий стрелка-радиста, при количестве ящиков равного ПЯТИ:
(1,2,3,4,5) 2 (2,3,4,5) 3 (1,3,4,5) 4 (2,4) 4 (1,3) 3 (2) 2.
Но дело в том, что если бы мы убили крысу, то об этом не узнали бы.
Значит необходимо загнать уже мертвую крысу в тот ящик, в котором она(крыса) навернека будет(но об этом мы опять не узнаем. :D

Аватара пользователя
ХМАО
Писатель на заборах
Писатель на заборах
Сообщения: 154
Зарегистрирован: 24 апр 2009, 21:15
Пол: Мужской
Откуда: ХАНТЫ-МАНСИЙСК

Re: Ловля крыс

Сообщение ХМАО »

Не понял!
А куда делся АВТОР, этой классной головоломки.

Шквал
Читатель
Читатель
Сообщения: 1
Зарегистрирован: 10 авг 2009, 14:47
Пол: Мужской

Re: Ловля крыс

Сообщение Шквал »

Может не париться и пальнуть вдоль ряда через все коробки разом? :D

Аватара пользователя
maksim82
Популярный автор
Популярный автор
Сообщения: 1813
Зарегистрирован: 28 июн 2005, 17:28
Пол: Мужской
Откуда: Москва

Re: Ловля крыс

Сообщение maksim82 »

ХМАО писал(а):Не понял!
А куда делся АВТОР, этой классной головоломки.
Ну дык все же вроде правильно)) то же самое, когда коробок 1000.

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Re: Ловля крыс

Сообщение Dendr »

ХМАО писал(а):Не понял!
А куда делся АВТОР, этой классной головоломки.
Эк вас. :D
Насчет автора понятия не имею. Американец какой-нибудь.
Спросите у Генриха Лиговского - я задачку у него на форуме "стырил".

Аватара пользователя
molch64
Литератор-любитель
Литератор-любитель
Сообщения: 266
Зарегистрирован: 08 июн 2006, 11:05
Пол: Мужской

Re: Ловля крыс

Сообщение molch64 »

Я тут слеганца, извиняюсь, что поднял тему трехлетней давности. :roll:
Вдруг кто вспомнит эту задачу. Так вот, тугоухая на 3 ящика крыса все же не прибивается. Никак.
Доказано для количества ящиков от 8 до 15 программно перебором всех вариантов.
Живучая, гадина. :D
За двумя заяйцами погонишься - ни одного заяйца не поймаешь!

Ответить

Вернуться в «Задачки»