Задачка

[andrzejn]

В глубине детского хлама безнадёжно затеряны старые наручные электронные часы. Раз в час они пищат. Полсекунды. Время на часах сбито, поэтому пищат не в точное время. Когда именно - всякий раз забываю засечь. Пищат уже третий месяц. Батарейки, судя по всему, хватит ещё надолго. Как бы эту звучалку изловить?

Нет, правильного ответа я и сам не знаю.

Comments

[kachur-donald.livejournal.com]

у меня аналогичная проблема, только пищат они в начале первого ночи и довольно долго.
тоже найти не могу уже полгода.

[p_govorun.livejournal.com]

Я искал когда-то штуку, которая пищала каждые 30 секунд (индикатор CO, который забеспокоился, что у него садится батарейка). По звуку найти нереально: за время короткого писка направление засечь невозможно. Мне пришлось перекладывать все вещи в другой угол комнаты.

С часами хуже: перекладывать придётся по одной вещи в час. :-)

[shellesie.livejournal.com]

объявить детям квест с призом победителю

[funt-lixa.livejournal.com]

Самый правильный вариант, но мне бы так было не интересно :)

[himba.livejournal.com]

Никак. Пока батарейка не сядет, будут орать.
Скажите еще спасибо, что это не пушистые детские игрушки. Сваленные на моем балконе, они часто просыпаются среди ночи и начинают петь Чебурашкины песни, или кричать Fire! Fire!

[satinenok.livejournal.com]

О да, это страшно:
http://community.livejournal.com/malyshi/8731351.html

:)

[himba.livejournal.com]

Точно-точно, это про нас!
Еще мотоцикл там на балконе под порывом ветра съехал среди ночи, кнопка нажалась и он стал орать свою сигнализацию. Два часа молча проклинала тех, кто не может к машине подойти, пока не сообразила, что это у меня.

[satinenok.livejournal.com]

Мотоцикл - настоящий? Или игрушечные сейчас тоже выпускают с сигнализацией :)

[himba.livejournal.com]

Который детский, на батарее. Жмешь педаль, он едет.

[neon-fit.livejournal.com]

=)))

[veefore.livejournal.com]

Перебрать все вещи. Долго, но должно помочь :-)

[gds.livejournal.com]

Если часы находятся внутри какой-либо вещи, то максимально быстро задача решается за ceil(log_k(N)) циклов часов, где k -- количество куч, из которых звук будет определяться как "разный", и N -- количество вещей в куче.
Если часы находятся между вещами, предлагаю ленивый вариант: три кучи, из исходной кучи каждый раз перекладывать по паре вещей в промежуточную кучу, ждать следующего писка. Если он из промежуточной кучи -- разобрать (ведь там всего пара вещей) и решить проблему. Если он из конечной кучи, то бить себя по рукам и начать алгоритм сначала. Если писк в исходной куче, то промежуточную кучу отметить как чистую, перекинуть её в конечную кучу, выполнить следующий шаг алгоритма. Можно очевидным образом доработать алгоритм, и в результате доработки и нехитрых логических построений доказать корректность и завершимость данного алгоритма. Требует всего O(1) места (3 кучи)!11 Оптимизировано под лень и под малочисленность промежуточной кучи.
Если есть три равноправных места (одно чуть побольше), то можно в качестве предусловий шага алгоритма рассматривать случай: вещи распределены на три кучи, в одной из которых точно нет часов, в двух остальных они с вероятностью 1/2. В начале алгоритма -- одну кучу оставить пустой (та, в которой точно нет часов), а все вещи распределить на две кучи (которые по 1/2).

[funt-lixa.livejournal.com]

Убить их, направив на кучу микроволнового излучения. Надо заставить микроволновку работать с открытой дверцей.