ERUDITOR.RU
 →  Тема «Субмарина»
Субмарина
Вражеская субмарина находится где-то на числовой прямой (в одном из целых чисел). Она движется с какой-то скоростью (целые единицы в минуту). Вам неизвестно ни ее местонахождение, ни ее скорость. Каждую минуту вы можете отправить одну торпеду в любое число. У вас есть бесконечный запас времени и торпед.

Задача: Придумать стратегию обстрела, которая в итоге гарантирует поражение субмарины.
↓↓ 0 ↑↑   Zero (38 / 335)   2008-09-02 23:05   »»


Хорошая задачка :-)
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-09-03 00:07   «« #2 »»   Ответить


Я правильно понял, что речь именно о целых (а не натуральных) числах?
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-09-07 17:24   «« #3 »»   Ответить


Правильно. Именно о целых.
↓↓ 0 ↑↑   Zero (38 / 335)   2008-09-08 12:20   «« #4 »»   Ответить


На самом деле всё равно, целые или натуральные.

Пусть x -- начальная координата, v -- скорость.

Для каждого начального условия (x,v) мы можем определить положение лодки в текущий момент t: x(t)=x+vt. А множество (x,v) явно счётно, поэтому просто перебираем их любым способом (например, по классической квадратной спирали), тратя на проверку каждого варианта ровно по одному выстрелу (стреляем в точку x+vt). Таким образом, мы гарантированно поразим субмарину, находившуюся изначально в точке (x,v) за не более чем (2*max(x,v)+1)^2 (это размер квадрата, в котором точно лежит точка (x,v)) выстрелов.
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-09-13 19:30   «« #5 »»   Ответить


Классическая квадратная спираль -- это один из способов пересчитать все целые точки на плоскости. Начинаем в нуле (0,0). Потом шагаем, например, направо (1,0), вниз (1,-1), влево (0,-1), влево (-1,-1), и т.д. разворачиваем спираль вокруг центра: (-1,0)-(-1,1)-(0,1)-(1,1)-(2,1)-(2,0)-(2,-1) и т.д.

Так мы пересчитываем все целые точки (х,у), перенумеровываем их, т.е., научным языком, выстраиваем взаимнооднозначное соответствие между целочисленными точками плоскости (х,у) и натуральным рядом.
↓↓ 0 ↑↑   eruditor (143 / 443)   2008-09-16 21:32   «« #6 »»   Ответить


?
Что-то я потерялся. По-моему, в _движущуюся_ субмарину, не зная её скорости так просто гарантированно не попадёшь :)
↓↓ 0 ↑↑   -V@Ndal- (7 / 31)   2008-12-27 22:55   «« #7 »»   Ответить


eruditor
Извините, конечно, математик я, наверное, никакой, но это не решение.
Поясняю:
Большой Бессмертный Вечносытый Заяц(ББВС)прыгает всегда на 2 метра. Маленький Бессмертный Вечносытый Заяц(МБВС) на 1 метр. ББВС стоит на метр впереди МБВЗ. Они одновременно начинают прыгать. Далее...
1) МБВЗ пройдет по всем точкам, на которых был ББВЗ? Ответ:Да!
2) Зайцы когда-нибудь окажутся в одной точке? Ответ:Нет!
↓↓ 0 ↑↑   Paha (0 / 62)   2009-01-06 00:53   «« #8   Ответить


 →  Тема «Субмарина»

Чтобы ответить на конкретное сообщение, нужно нажать на ссылку «ответить» справа под самим сообщением.
Эта форма — для ответов на исходное сообщение темы (на всю тему в целом).
© 2006-2024   Авторы