>> | №18652 #157 А я проходил каким-то жутко странным алгоритмом решения за O(N^2) шагов с O(N) памяти. - Зажигаем все, гасим и зажигаем обратно те, что случайно угадались.
- Гасим и зажигаем обратно каждую из лампочек по очереди. Ровно одна угадывается. Помечаем её как N и гасим.
- Аналогично, пусть у нас зажжены все лампочки кроме N-K+1, N-K+2, ..., N-1, N. Гасим и зажигаем обратно каждую из оставшихся лампочек по очереди. Ровно одна угадывается. Помечаем её как N-K и гасим.
- Повторяем 3. до тех пор, пока не останется ровно одна лампочка. Она - первая.
- Перещёлкиваем первую лампочку. Зажигаем лампочки с метками 2, 3, ..., N.
>>18648 Ты, кстати, где-то ошибся во время первого прохождения. У меня твоим методом получается на каждом круге угадать ровно одну лампочку из оставшихся, они как раз в точности соответствуют лампочкам 1, 2, 3, ..., N из моего решения. К слову, твоё требует тот же порядок кликов, но не требует памяти. |