Комментарии 17
Подпишусь на ответы)
Если белые и черные клетки встречаются только один раз (проверила, покликав на клетки), то нам поможет бинарный поиск.
Зарегистрировался, чтобы ответить, нашел, правда у меня ощущение, что клетки генерируются в зависимости от кликов. Одинаковые клики, одинаковый результат
Метод дихотомии не подвёл ни разу. Было где-то 8 попыток.
Бинарный поиск, хорошо, а как из условия понять что переход белое -> черное только один?
Напомнило классическую историю о 64 блокерах и продаванах чудо софта по предсказанию рынка. Типа, в первый месяц отправили по 32 прогноза на рост и 32 на падение, потом оставшимся верно угаданным по 16, потом по 8 потом по 4, и паре последних уверившихся в 6 абсолютно точных прогнозов продали суперсофт по миллиону долларов за экземпляр. Бинарный поиск рулит, но ваша программка жульничает выдавая всегда наихудший вариант для угадателя.
По описанию думал, что клетки "либо чёрные, либо белые", а по факту последовательность белых, которые где-то переходят в последовательность чёрных.
Первую задачу в 5 кликов не решить, вторую - легко.
Вот анимация решения. Интересно, что решение никак не опирается на то, что в последовательности есть всего один переход от белого к чёрному. После того, как мы узнали цвет центральной клетки, у нас уже получилась задача вдвое меньшего размера.
Бинарный поиск. Неважно, что там с количеством переходов и количеством соседей одного цвета. После любого клика в середине мы получаем два полуотрезка, у одного из которых концы разного цвета. Над ним и издеваемся на следующем шаге. Для 20 клеток надо roundup(log2(20-1)) = 5 попыток.
А можно сделать так, чтобы цвета не подстраивались под мой поиск? Я чуть не сошёл с ума, пытаясь понять, почему по статистике мой путь поиска не сокращался.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Собеседование по алгоритмам: разноцветные соседи Есть двадцать клеток, каждая из которых либо белая, либо чёрная....