Коллеги рассказали задачку

[antilamer]

Есть бесконечная река с пристанями, пронумерованными всеми целыми числами (..., -2, -1, 0, 1, 2, ...). По реке плывет корабль-призрак, из неизвестной начальной точки, с фиксированной, но неизвестной целочисленной скоростью - т.е. для каких-то неизвестных a, b в день i корабль останавливается в пристани ai+b

Comments

[djuffin]

Нужно спиралью от (0,0) пронумеровать все элементы множества Z x Z. И для каждого дня i брать элемент этого множества (a, b) с номером i, и ехать на пристань ai+b.

[antilamer]

Ага. Можно обобщить - поймать корабль-призрак, движущийся по многомерному пространству по траектории, задаваемой неизвестной функцией из счетного семейства :)

[sassa_nf]

или ещё другими словами - найти изоморфизм (Int,Int)->Int

Хотя возможно изоморфизм (Int,Int)->Nat, т.к. в задаче не сказано, как нумеруются дни.

[plumqqz]

На бесконечной реке за конечное число шагов? Гм.

[aamonster]

Ну, мы же можем досчитать до любого из бесконечного множества натуральных чисел за конечное число шагов.

Вот до всех - другое дело.

[assaron]

Перебираем всю целочисленную плоскость в каком-нибудь порядке, например, по спирали от (0, 0), получаем последовательность (a_i, b_i). Наша функция f(i) = a_i + b_i * i. Соответственно, для любой заданной пары a, b будет конченое i, что f(i) = a + b * i, а именно, когда (a, b) = (a_i, b_i).

[aamonster]

Тупой вариант: нумеруем все прогрессии (upd: все пары a,b) (это несложно, есть много методов) и останавливаемся каждую ночь в значении очередной прогрессии по списку.

Но чую, что должно быть красивое решение...

[antilamer]

Это и так красивое :)

[aamonster]

Красивое - в смысле, упирающееся не в мощность множеств, а, скажем, в делимость. Что-нибудь в виде явно записанной функции, а не через перебор последовательностей.

[sassa_nf]

нутк, это ж через решение квадратного уравнения делается.

Все точки квадранта перечисляются как разложения числа на сумму двух чисел:

0 = (0+0)
1 = (1+0), (0+1)
2 = (2+0), (1+1), (0+2)
...

итак, перечисляются ряды треугольника. Номер ряда n можно вычислить из округления вверх решения квадратного уравнения n*(n+1)=2*i, номер точки в ряду из i и номера ряда тоже.

Тогда четыре квадранта перечисляются последовательно (номер точки в квадранте, квадрант) = (i / 4, i % 4).