Задача о болтах и гайках

[venco]

На самом деле я уже погуглил - эта задача довольно долго была нерешённой, но в конце концов нашли алгоритм с $O(N\log N)$ сравнений. Он сводится к делению, как предложил hurtsy, но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.

[hurtsy]

venco в сообщении #462118 писал(а):

но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.

Да, стратегия выбора обязана быть нетривиальной. Но ведь если некто(типа демона Максвелла, естественно не нарушая условий, а это возможно) будет подсовывать Вам наименьший элемент, не на чем будет строить выбор и быть квадратичности. Собственно, топик стартер об этом говорил, без привлечения ДМ. С уважением,

[venco]

hurtsy в сообщении #462203 писал(а):

venco в сообщении #462118 писал(а):

но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.

Да, стратегия выбора обязана быть нетривиальной. Но ведь если некто(типа демона Максвелла, естественно не нарушая условий, а это возможно) будет подсовывать Вам наименьший элемент, не на чем будет строить выбор и быть квадратичности. Собственно, топик стартер об этом говорил, без привлечения ДМ. С уважением,

Ну у нас есть возможность потратить порядка $N$ сравнений для выбора более-менее среднего элемента, чтобы не ухудшить общую сложность $N\log N$.

[hurtsy]

venco в сообщении #462232 писал(а):

Ну у нас есть возможность потратить порядка $N$ сравнений для выбора более-менее среднего элемента, чтобы не ухудшить общую сложность $N\log N$.

Согласен. Просто "тему жалко". В итерационных методах для конечных разностей самая большая радость заменить $N$ на $\log N$. С уважением,

[Circiter]

(Похожая задачка :))

Неподскажите, можно ли решить такую похожую задачку. Есть всего две гайки разного диаметра и два болта разного диаметра, нужно разместить гайки по возрастанию диаметра и болты, тоже по возрастанию диаметра, используя только сравнения диаметров изделий разного типа (как в исходной задаче). Заметьте, для гайки/болта необязательно существует комплементарное изделие того же диаметра. Но если для каждого изделия это условие выполняется, то задача эквивалентна исходной при $N=2$. Возможно ли решение в общем случае (но изделий каждого типа все-равно только две штуки)? Заранее спасибо.

[venco]

(Похожая задачка :))

Circiter в сообщении #462808 писал(а):

Неподскажите, можно ли решить такую похожую задачку. Есть всего две гайки разного диаметра и два болта разного диаметра, нужно разместить гайки по возрастанию диаметра и болты, тоже по возрастанию диаметра, используя только сравнения диаметров изделий разного типа (как в исходной задаче). Заметьте, для гайки/болта необязательно существует комплементарное изделие того же диаметра. Но если для каждого изделия это условие выполняется, то задача эквивалентна исходной при $N=2$. Возможно ли решение в общем случае (но изделий каждого типа все-равно только две штуки)? Заранее спасибо.

Нет. Возьмите два очень маленьких болта и две очень больших гайки.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.