?

Log in

No account? Create an account

Задачка типа интервьюшной - Общество дровосеков Бердичева по изучению Мишны

Jan. 11th, 2010

02:25 pm - Задачка типа интервьюшной

Previous Entry Share Next Entry

Экс-сослуживец прислал задачку (с сабжектом "easy submarine puzzle"):

A submarine is in an arbitrarily long canal moving at a fixed velocity. Every second you get to probe for it at a given location in the canal (the probe covers some specific, fixed distance in the canal, and the velocity is an integer multiple of that distance/second). How do you find the velocity of the sub and its location when you started probing?
Подводная лодка1 равномерно движется в канале неограниченной длины. Каждую секунду можно сканировать2 отрезок канала определенной фиксированной длины на предмет нахождения там подлодки; известно, что её скорость кратна длине отрезка в секунду. Как найти скорость и положение лодки на момент начала сканирования?

1) Длина лодки произвольно мала, но больше нуля.
2) В течение всей секунды, если угодно.

Комменты, понятное дело, скринятся.

Upd: Чтобы мне не повторяться, перед ответом просмотрите расскриненные комментарии.

По здравом размышлении, задачка действительно вполне easy. Я дал правильный ответ со второй попытки (первый вариант заботился лишь о том, чтобы гарантированно "обогнать" лодку, а не отловить ее в "нужное" время в "нужном" месте).

malaya_zemlya первым дал правильный ответ.

Comments:

From:saccovanzetti
Date:January 11th, 2010 10:31 pm (UTC)
(Link)
а скорость постоянна?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 11th, 2010 10:35 pm (UTC)
(Link)
В условии есть слово "равномерно". Этого должно быть достаточно, чтобы понять, постоянна ли скорость лодки.
(Reply) (Parent) (Thread)
From:saccovanzetti
Date:January 11th, 2010 10:50 pm (UTC)
(Link)

какой-то странный сонар у них. если скажем лодка движется со скоростью 10 м/с, а пробник - шириной в 1 метр, то так лодку можно и вообще не обнаружить, если каждую секунду только можно запрашивать - даже если этих пробников вагон вдоль ее движения. может, все наоборот - радары широкиe, гораздо шире дистанции, проходимой лодкой в 1 секунду ?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:02 pm (UTC)
(Link)
Нет, всё именно так, как написано. Сканировать можно ровно один "единичный" интервал в секунду.
(Reply) (Parent) (Thread)
From:saccovanzetti
Date:January 11th, 2010 11:20 pm (UTC)
(Link)
тогда необходимо предположить,

- что длина самой лодки больше или равна дистанции, проходимой ею в секунду
- что известно направление движения лодки
- двигаться от конца канала к началу через равные единичные интервалы, запеленговать лодку. как только лодка найдена, вернуться назад на расстояние, заведомо большее длины корпуса лодки + скорость и пингать на одном месте.

(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:25 pm (UTC)
(Link)
Да нет же. Длина лодки произвольно мала, направление движения неизвестно. Всё написано в условии.
(Reply) (Parent) (Thread)
From:saccovanzetti
Date:January 11th, 2010 11:28 pm (UTC)
(Link)
не понял - если она произвольно мала и направление неизвестно, то пока мы зондируем крайнюю левую точку канала, она покидает канал из крайней правой точки и тю-тю. arbitrarily long - is not infinitely long
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:34 pm (UTC)
(Link)
arbitrarily long - is not infinitely long

Ему и не надо быть infinitely long. Достаточно быть, скажем, длины "N-я сверхстепень от N-й сверхстепени от N", где N - сумма модулей скорости лодки и начального смещения. Если мало, можно приписать "N-я сверхстепень" еще N раз.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:46 pm (UTC)
(Link)
Длина канала "потенциально" бесконечна. Т.е. гарантированно достаточна для того, чтобы поймать лодку при использовании оптимального алгоритма, но наперед неизвестна.
(Reply) (Parent) (Thread)
From:saccovanzetti
Date:January 11th, 2010 11:42 pm (UTC)
(Link)
в исходном условии про начальное смещение ничего нет. это дополнительное условие, что остаток длины канала вдоль направления движения лодки существенно превосходит начальное смещение?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:51 pm (UTC)
(Link)
Упрощу условие: канал бесконечный.
(Reply) (Parent) (Thread)
From:saccovanzetti
Date:January 12th, 2010 12:01 am (UTC)
(Link)
что-то с рядом Фиббоначи, имхо, должно быть связано.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:January 12th, 2010 12:11 am (UTC)
(Link)
Не знаю; из моего решения это неясно.

Из ожидаемого решения должно быть очевидно, что при любых наперед заданных скорости и смещении лодка будет поймана не позднее, чем некоторая функция от модулей скорости и смещения.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:03 pm (UTC)
(Link)
Равномерного распределения на неограниченных интервалах не бывает.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:08 pm (UTC)
(Link)
Это очевидным образом не работает, потому что, скажем, лодка, находящаяся вначале в точке 3 и удаляющаяся в положительном направлении со скоростью 3, найдена не будет.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:23 pm (UTC)
(Link)
Потому что интервал поиска растет медленнее, чем линейно.
(Reply) (Parent) (Thread)
(Deleted comment)
[User Picture]
From:spamsink
Date:January 11th, 2010 11:47 pm (UTC)
(Link)
И как это изменит асимптоту? Все равно сублинейно получается.
(Reply) (Parent) (Thread)
[User Picture]
From:malaya_zemlya
Date:January 12th, 2010 05:57 am (UTC)
(Link)
Если у нас уже есть алгоритм нахождения лодки, то все просто: запускаем алгоритм два раза, вычтитаем, делим.

Алгорити следующий. Предположим, что лодка плывет со скоростью v и начинает с положения х0. Иными словами уравнение ее движения x(t)=v*x+x0

Перебираем все пары <v,x0>. Любым удобным способом. Находим соответсвующий x, сканируем (x,x+1)

В какой-то момент лодка найдется, клянусь своей треуголкой.
(Reply) (Thread)
[User Picture]
From:zebra24
Date:January 14th, 2010 07:04 pm (UTC)
(Link)
надо перебирать целые коэффициенты a / b из x = at + b
по правилу типа
a___b
n [-n..n]
-n [-n..n]
n меняется от нуля до наибольшего из искомых чисел a/b.

Xk - участок на котором делается очередная проверка

Xk = nt -n
Xk+1 = nt -n+1
..
Xk+2n = nt + n
..
Xk+2n+1 = -nt - n
Xk+2n+2 = -nt - n+1
..
Xk+4n = -nt + n

при этом можно попытаться уменьшить перебор, исключив проверки, отсекаемые

после того, как нашли лодку в одной точке остальное дело техники.
Если радар позволяет определить скорость наблюдаемой лодки, задача решена.
Если нет, решаем уравнение:
В точке Xn, Tn была замечена лодка

Xn = aTn + b
=>
b = aTn - Xn

x = at + aTn - Xn
x = a*(1+Tn) t - Xn

известно, что а целое число, продолжаем такой-же поиск.
a = 0, -1, 1, -2, 2, -3, 3, -4, 4...
На какомнить шаге находим лодку, и коэфф. а.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:January 14th, 2010 07:15 pm (UTC)
(Link)
Правильно.
(Reply) (Parent) (Thread)