связанный список

[rrrFer]

Спасибо, я почувствовал себя овощем )
у меня получилось в продолжение моего предыдущего решения, лишь предел для x опеределить (по китайской теореме об остатках выходит что x не больше B*B) но тут и сложность смахивает на квадратичную и точных значений нет...).

[Sibedir]

Сообщение от rrrFer

я почувствовал себя овощем

Ну и зря. Я вот понятия не понял о чем тут речь

Сообщение от rrrFer

по китайской теореме об остатках выходит ...

Ну а по этой самой теореме что получается при В>1?

сложность смахивает на квадратичную и точных значений нет...

Точных нет. А точнее - нет конкретных. Для определенной длины списка существует, я так понимаю, min и max сложности. Конкретное значение зависит от отношения A/B.

И последнее, rrrFer вообще не советовал бы мои математические выкладки принимать на веру. Я и сам-то в их правильности не уверен. Хотел лишь передать ход мыслей.

[rrrFer]

Ну а по этой самой теореме что получается при В>1?

A = nB-x

т.е. у тебя вышло x = nB - A;
по теореме (если я ее верно исопльзовал) вышло
х < (B*B - (A mod B)) / 2
вобщем сложность квадратичная, а значит, если подставить в то, что вышло у тебя, в худшем случае n = B (т.е. второму (быстрому) указателю в худшем случае придется сделать B циклов.

Я и сам-то в их правильности не уверен.

но я тоже неуверен в своих )

[Sibedir]

У меня x - это число шагов сделанных медленным указателем по циклу (от начала цикла до того места, где быстрый его догнал). Привожу схему. Немного откорректировал ИД для удобства расчетов. Теперь B = N-A+1
Схема 1.jpg
И вот этот х не может быть вольше B, ну ни как. Ведь с момента, когда М зашёл в цикл, расстояние м/y М и Б с каждым ходом начнет уменьшаться на 1 --->
Б не сможет "нерепрыгнуть" ч/з М --->
X < B (X=0 когда А кратно В)
Вот в этом выводе я уверен на 100%

Что же касается n.
путь Б = 2 * путь М
A+nB+x = 2(A+x)
n = (A+x)/B
n = A/B + x/B
т.к. x/B < 1
n = A/B - при A кратном B
n = (A div B) + 1 - иначе