Условие
Системный администратор Олег обслуживает вычислительный кластер экспериментального термоядерного комплекса. Инфраструктура состоит из 1000 серверов, на которых хранятся данные телеметрии, результаты расчетов и резервные копии критически важных систем.
Однажды специалисты заметили проблему: на одном из серверов появился неизвестный вирус. Он не нагружает процессор, не генерирует подозрительный сетевой трафик и не оставляет следов в системных журналах. Единственное проявление — раз в сутки вирус незаметно повреждает один файл резервной копии.
Для поиска зараженного узла Олег написал специальный анализатор логов. Скрипт может проверять любое количество серверов одновременно, объединяя их журналы в единый пул. Результат проверки может быть только двух видов:
- Status: 500 — если среди проверяемых серверов есть зараженный;
- Status: 200 — если зараженного сервера в группе нет.
Однако есть серьезное ограничение. Анализатор настолько сильно нагружает сеть и системы хранения данных, что его разрешено запускать не более 10 раз в сутки. Более того, все проверки должны быть спланированы заранее и отправлены в расписание на весь день. Изменять состав очередной проверки после получения результатов предыдущей нельзя.
Задача
Олегу нужно гарантированно определить единственный зараженный сервер всего за сутки. Предложите стратегию, которая позволит гарантированно определить один зараженный сервер из 1000 возможных за 10 запусков анализатора. Напишите код на Python, который по результатам проверок сможет определить номер зараженного узла.
Решение
Сначала рассмотрим решение, которое многие предложат интуитивно. Самый логичный вариант — разделить серверы пополам и проверить одну из половин. Если анализатор вернул Status: 500, вирус находится в этой группе. Если Status: 200 — в другой. После этого оставшуюся группу снова можно разделить пополам и повторить процедуру.
Классический бинарный поиск для 1000 серверов действительно проходит в 10 этапов:
- 1000 → 500;
- 500 → 250;
- 250 → 125;
- 125 → 63 (и 62);
- 63 → 32 (и 31);
- 32 → 16;
- 16 → 8;
- 8 → 4;
- 4 → 2;
- 2 → 1.
Вроде все просто, но на поверку такой подход не подходит под условия задачи. Проблема в том, что каждая следующая проверка зависит от результата предыдущей. Мы не можем заранее определить состав второй группы, пока не узнаем результат первой проверки. По условию же все десять запусков должны быть подготовлены заранее.
Диагностика через двоичное представление состояния
Каждая проверка имеет только два возможных исхода: «Status: 200» или «Status: 500». Фактически один запуск анализатора сообщает нам один бит информации. Тогда десять запусков дают: 2¹⁰ = 1024 различных комбинации результатов. А серверов всего 1000. Следовательно, каждому серверу можно сопоставить уникальную последовательность из десяти битов.
Пронумеруем серверы от 0 до 999. Каждый номер запишем в двоичном виде с использованием десяти разрядов. Например:
- 13 → 0000001101
- 537 → 1000011001
- 999 → 1111100111
Теперь каждый бит будет отвечать за одну проверку. Далее сформируем группы:
- Первая проверка включает все серверы, у которых установлен младший бит.
- Вторая проверка включает все серверы, у которых установлен второй бит.
- Третья — все серверы с установленным третьим битом.
И так далее до десятой проверки. Таким образом каждый сервер участвует в уникальном наборе проверок. Теперь нам нужно определить зараженный сервер. Предположим, после суток работы мы получили такие результаты: 500, 200, 500, 500, 200, 200, 200, 200, 200, 200. Заменим ошибки на единицы, а успешные проверки на нули. Получаем последовательность бит 1,0,1,1,0,0,0,0,0,0 — где первый бит соответствует младшему разряду (2⁰), а последний — старшему (2⁹). Развернув порядок (от старшего разряда к младшему), получаем привычную двоичную запись 0000001101, что соответствует числу 13.
Реализуем решение на Python
Для автоматического формирования групп можно использовать следующий код. Для удобства он разделен на несколько частей.
# --- ЧАСТЬ 1: Формируем расписание проверок ---
num_tests = 10
# Создаем 10 пулов для серверов (для тестов от 1 до 10)
tests_pools = {i: [] for i in range(1, num_tests + 1)}
# Проходим по серверам от 0 до 999, как указано в условии
for server_id in range(1000):
for bit_position in range(num_tests):
# Если в двоичной записи номера сервера стоит 1 на нужной позиции
if (server_id >> bit_position) & 1:
# Назначаем сервер в тест (номер теста = позиция бита + 1)
tests_pools[bit_position + 1].append(server_id)
Во второй части проверяем работу алгоритма и получаем результат.
# --- ЧАСТЬ 2: Функция поиска виновника ---
def find_infected_server(statuses: list) -> int:
"""
Принимает список из 10 статусов (от 1-го теста к 10-му).
Возвращает десятичный номер зараженного сервера (от 0 до 999).
"""
infected_id = 0
for bit_position, status in enumerate(statuses):
if status == "Status: 500":
# Если тест упал, выставляем единицу в соответствующий бит
infected_id |= (1 << bit_position)
return infected_id
# --- ПРОВЕРКА РАБОТЫ АЛГОРИТМА ---
# Пример из условия: 1-й, 3-й и 4-й тесты выдали ошибку, остальные — чисто.
# В условии это строка 1011000000 (читается справа налево, где младший бит — первый тест)
sample_statuses = [
"Status: 500", # 1-й тест (младший бит) -> 1
"Status: 200", # 2-й тест -> 0
"Status: 500", # 3-й тест -> 1
"Status: 500", # 4-й тест -> 1
"Status: 200", # 5-й тест -> 0
"Status: 200", # 6-й тест -> 0
"Status: 200", # 7-й тест -> 0
"Status: 200", # 8-й тест -> 0
"Status: 200", # 9-й тест -> 0
"Status: 200", # 10-й тест (старший бит) -> 0
]
result = find_infected_server(sample_statuses)
print(f"Количество серверов в первом запуске: {len(tests_pools[1])}")
print(f"Полученный лог лаборатории: {sample_statuses}")
print(f"ВНИМАНИЕ! Вирус обнаружен на сервере №: {result}")
# Двоичное 1101 в десятичной системе — это 13.
Решение работает, так как каждый сервер имеет собственное уникальное десятибитное представление. Поскольку десять проверок могут породить 1024 различных комбинации ответов, а серверов всего 1000, двух серверов с одинаковым набором результатов не существует. Следовательно, получив результаты всех проверок, мы всегда сможем однозначно определить заражённый сервер.
Заключение
Если бы Олег мог менять состав групп после каждой проверки, задачу можно было бы решить обычным бинарным поиском. Однако из-за высокой нагрузки анализатора все проверки приходится планировать заранее. В таких условиях бинарный поиск перестаёт работать, зато помогает идея из двоичной системы счисления.
