Ловля крыс

[Dendr]

Дык что тогда? По два выстрела в каждую коробку подряд кроме первой и последней - и хозяева крысы в трауре...

Ну... близко к правде, да не совсем. (разделить-то уже озвученный правильный ответ 1996 на два - дело нехитрое;))

Нужно разбить задачу на подзадачи.
Даю намётку:
Перед первым выстрелом крыса может находиться в любой коробке.
Если мы сделаем выстрел, и после него крыса сможет опять оказаться где угодно - то мы вернемся к самому началу, ничего не изменится. Следовательно, этот выстрел - лишний. Нужно стрелять так, чтобы стало заведомо известно, что она точно не может находиться в ящиках с номерами, например, 35, 678 и 802. Разумеется, конфигурация после каждого выстрела должна меняться, но не повторяться. Рано или поздно мы придем к тому, что крыса должна находиться только в одном ящике (а если она очень хитрая, то так и будет). Туда, изверги такие, мы и выстрелим.

крыска все-таки жива. Ирис скажет мне спасибо. Гринпис форевер...

Хм... Давайте считать, что это вредная крыса. И мы так должны спасти от нее ценный груз морковки, который везут африканским детям.

[Шшок]

А, ну да, опять фигню спорол... После второго выстрела по второй коробке крыса может перейти из третьей во вторую - и остаться живой...
Опять гринпис торжествует.

[molch64]

Если мы сделаем выстрел, и после него крыса сможет опять оказаться где угодно - то мы вернемся к самому началу, ничего не изменится. Следовательно, этот выстрел - лишний. Нужно стрелять так, чтобы стало заведомо известно, что она точно не может находиться в ящиках с номерами, например, 35, 678 и 802. Разумеется, конфигурация после каждого выстрела должна меняться, но не повторяться. Рано или поздно мы придем к тому, что крыса должна находиться только в одном ящике (а если она очень хитрая, то так и будет). Туда, изверги такие, мы и выстрелим.

Честно говоря я не понял, что ты имел в виду в этом намеке.
Кроме идей выделить из вида "крысус обыкновентус" подвиды "крысус чётнус" и "крысус нечётнус" я не понимаю как эту задачу решать;)

[Dendr]

Честно говоря я не понял, что ты имел в виду в этом намеке.
Кроме идей выделить из вида "крысус обыкновентус" подвиды "крысус чётнус" и "крысус нечётнус" я не понимаю как эту задачу решать;)

Эта идея - частный случай моего опуса.
Основной мой посыл - после каждого выстрела число заведомо пустых коробок не убывает.
В принципе, ведь тут можно написать программку (наподобие Life, только не саморазвивающаяся) - и уж тут, кстааати, можно загонять и тугоухую крысу...

[molch64]

В принципе, ведь тут можно написать программку (наподобие Life, только не саморазвивающаяся) - и уж тут, кстааати, можно загонять и тугоухую крысу...

Во-во... А я тем временем пока не грохнул тугоухую на >3 коробок крысу... Может, все-таки её грохнуть нельзя?

[Slavaa]

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

[Valentin]

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

А можно допустить что она сидит в третьей коробке, и тогда после второго выстрела она таки имеет полное право в этой первой коробке быть.

[Шшок]

Все-таки у меня ничего не получается. Что бы я ни делал, у меня при любой стратегии получается, что в момент перехода от одной коробки к другой крыса всегда может переместиться в ту коробку, по которой я только что сделал выстрел.
Получается точно как у Жванецкого: Захочешь шлепнуть ее по попе, а рука попадает в то место, где она только что была...

[Dendr]

Все-таки у меня ничего не получается.

Вы все мучаетесь с 1000 коробок? Тогда мы идем к вам

Индукция, коллеги.
А что, если коробок всего 3? Ну или 4? После 5 коробок принцип уже понятен.

[Шшок]

Ладно, попробуем порассуждать.

Три коробки - все просто. Стреляем дважды в среднюю коробку - и нет крысы.
Четыре коробки: делаем выстрел по второй коробке. После этого выстрела крыса уже может находиться не в любой коробке, а только во второй, третьей или четвертой. В первой ее никак не может быть.
Что нужно делать, чтобы следующим выстрелом исключить из рассмотрения еще какую-нибудь коробку, и при этом снова случайно не включить в рассмотрение первую??? Ответ: снова выстрелить по второй. Но после этого выстрела крыса может перебраться из третьей коробки во вторую... и нам снова надо палить по второй. И так до бесконечности...
Значит, второй выстрел по второй коробке нам ничего не дает...
Все равно не складывается. Будем думать дальше.

[Инна]

У меня тоже порядка 2000 получается.
Если изначально крыса в коробке с четным номером, то за 1000 найдется, если - с нечетным, то на второй тысяче.
А вот если бы крыса могла оставаться на месте, то решения не было бы, если только нельзя хотя бы два выстрела подряд делать.

[Dendr]

"Порядка 2000" - это не тот ответ, который я бы ожидал.

К тому же - мы абсолютно не знаем, где крыса. И не знаем, попала ли пуля в цель или нет.

[Инна]

"Порядка 2000" - это не тот ответ, который я бы ожидал.
.

Я имела в виду, что если ряд длины N, то ответ будет 2N-С, где С - константа

К тому же - мы абсолютно не знаем, где крыса. И не знаем, попала ли пуля в цель или нет

Поняла, тогда в любом случае надо доводить алгоритм до конца. Получается
998+998

[Филь]

Четыре коробки: делаем выстрел по второй коробке. После этого выстрела крыса уже может находиться не в любой коробке, а только во второй, третьей или четвертой. В первой ее никак не может быть.

А если тут применить теорию чётных и нечётных крыс? Стреляем дальше в третью коробку. Если у нас изначально была чётная крыса, то либо она сдохла от первого выстрела в коробку-2, либо находится теперь в коробке-3 и умрёт от второго.

Если у нас изначально была нечётная крыса, то после двух выстрелов она может быть либо в коробке-1 либо в коробке-3. Стреляем в третью. Потом во вторую. Вроде всё, убили.

Теперь надо как-нибудь обобщить на большее количество коробок.

[Versus]

Теперь надо как-нибудь обобщить на большее количество коробок.

Почему "как-нибудь"? Самым непосредственным образом. Сначала простреливаем слева-направо все коробки, в которых может сидеть чётная крыса. Тунелировать сквозь "нечётную" (в кавычках) коробку крыса не может, так что ей не жить. Потом в обратном порядке простреливаем коробки для "нечётной" крысы. В итоге обе крысы мертвы.

На практике это выглядит так:

2, 3, 4....n-1
n-1, n-2, n-3....2

итого 2*(n-2) выстрелов, как сказали в самомо начале.

Для глухой крысы, видимо, придётся разбить всё пространство на блоки, ограниченные радиусом слуха крысы. И простреливать их по очереди в определённом порядке. Но тут надо ещё подумать надо оптимизацией процесса.