Любите ли Вы Brainstorm так,

[menato]

как люблю его я.

Речь вовсе не о Латвийском коллективе. Сегодня Саша Куликов aka kirpich_spb предложил интересную задачку по алгоритмике

Comments

[jack239]

=)

[menato]

Это запрос? :)

[worlds_owner]

.

[menato]

А это запрос на условие? :)

[worlds_owner]

Да вроде.

[jp_bur]

А можно условие? =) Интересно же =)

[menato]

Имеется массив чисел длины n+1. Его элементы -- числа от 1 до n. Имея константное число дополнительных переменных и доступ к массиву только на чтение, найти за линейное время повторяющийся элемент. (Стандартно: битов - их уже log n, но операции с числами за O(1)).

[burunduk1]

А условие можно?)

[menato]

Имеется массив чисел длины n+1. Его элементы -- числа от 1 до n. Имея константное число дополнительных переменных и доступ к массиву только на чтение, найти за линейное время повторяющийся элемент. (Стандартно: битов - их уже log n, но операции с числами за O(1)).

[worlds_owner]

Это что, шутка? Просто посчитай сумму.

[menato]

Числа могут повторяться разное число раз, могут не встречаться. Просто есть одно ограничение на множество, откуда они берутся.

[dmitri_pavlov]

Так а что за задача-то?

[menato]

Ты наверно знаешь. Имеется массив чисел длины n+1. Его элементы -- числа от 1 до n. Имея константное число дополнительных переменных и доступ к массиву только на чтение, найти за линейное время повторяющийся элемент. (Стандартно: битов - их уже log n, но операции с числами за O(1)).

[dmitri_pavlov]

Да, это архиклассическая задача.
Надо всё проxorить.

[menato]

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