Задача была в финале
этого конкурса.
Я ее немного почистил от шелухи, чтоб звучало покороче. Решить мы ее не смогли, а разбора задач от организаторов не было. Очевидно, что она не решается в приемлимое время перебором ( я проверил :) Может кто подскажет в какую сторону смотреть ?
Компьютеры, подключены в сеть, имеют свои IP-адреса. Каждый IP-адрес представлен натуральным числом от 1 до 2^30.
Для блокирировки/разблокировки IP-адреса в Сеть посылается последовательность команд в виде натуральных чисел от 1 до 999.
Как работают эти команды ?
Команда «2 - воздействует на каждый второй IP-адрес, блокируя или разблокируя его, по правилу: если до выполнения этой команды IP-адрес не был заблокирован, то он блокируется, если IP-адрес был заблокирован, то он разблокируется.
Команда «3 - воздействует на каждый третий IP-адрес, блокируя или разблокируя его по тому же правилу.
Команда «4 - аналогичным образом воздействует на каждый четвертый IP-адрес,
команда «5 - на каждый пятый и т.д.
Понятное дело, что команда «1 воздействует на все IP-адреса (т.е. «на каждый первый IP-адрес), производя полную инверсию, когда все заблокированные IP- адреса разблокируются, а все незаблокированные блокируются.
Необходимо по имеющейся последовательности команд определить какое количество IP-адресов будет заблокировано после выполнения всех этих команд, при условии, что до этого в Сети не было заблокированных IP-адресов.
Исходные данные: массив натуральных чисел от 1 до 999
РЕЗУЛЬТАТ представьте в следующем виде:
Для последовательности команд: 2 6 8 3
Количество заблокированных IP-адресов 581 610 155
