Как решить задачу про блокировку адресов?

Question

[Вячеслав]

Задача была в финале этого конкурса.
Я ее немного почистил от шелухи, чтоб звучало покороче. Решить мы ее не смогли, а разбора задач от организаторов не было. Очевидно, что она не решается в приемлимое время перебором ( я проверил :) Может кто подскажет в какую сторону смотреть ?

Компьютеры, подключены в сеть, имеют свои 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

Comments

[Сослан Хлоев]

Роскомнадзор, перелогинься

Answer 1

[Tabris17]

Понятное дело, что надо считать только суммы изменений
У меня получилась примерно такая формула

Вот пример частного случая (я не предусматривал команду 1) ну и еще может какие-то нюансы не учел

spoiler

#include <iostream>
#include <cmath> 

using namespace std;

int GCD(int a, int b) { //наибольший делитель
	return b ? GCD(b, a%b) : a;
}

int LCM(int a, int b) { //наименьшее кратное
	return a / GCD(a, b) * b;
}

int main()
{
    
	int a[4] = { 2, 6, 8, 3}; 
	int k = 0; //счетчик заблокированных
	int n = pow(2, 30);
	int b = 1;
	for (int i = 0; i < 4; i++)
	{
		k += floor(n/a[i]);
		b = -1;
		for (int j = 0; j < i; j++)
		{
			k += floor(n / LCM(a[j], a[i])) *b *2;
			b *= -1;
		}
	}
	cout << "otvet " << k;
}

Добавлено:
если поставить 2, 4, 8, 3, а не 2, 3, 4, 8 то будет работать правильно
тут надо еще подумать и доработать знак который ставиться перед 2*(n/НОК(a1,a2))
надо выявить закономерность и правильно указать степень у -1

Comments

[Вячеслав]

Я тоже примерно так рассуждал. Для одного исходного числа:
k = n / a1
Для двух чисел:
k = n / a1 + n / a2 - 2*(n/НОК(a1,a2))
А вот дальше кратность НОКов тоже начинает влиять.

Поэтому вопрос по предложенной формуле: если сократить n до 2^5 = 32 тоже верно должно считаться ?
Если n=32, a[4] = { 2, 3, 4, 8}; то результат "otvet 2", метод перебора дает 14

Перебор на с++ как оказалось работает очень быстро. На 1С мне не удалось дождаться результата.
Для набора 2, 6, 8, 3 результат совпадает, а вот для 2, 3, 4, 8 результат значительно различается.

#include <iostream>
#include <cmath>.

using namespace std;

int main()
{
  int a[4] = { 2, 3, 4, 8};.
  int k = 0; //счетчик заблокированных
  int n = pow(2, 30);
  int b;
  for (int i = 1; i <= n; i++)
  {
    b = i % a[0] == 0 ? 1 : 0;
    b = i % a[1] == 0 ? 1-b : b;
    b = i % a[2] == 0 ? 1-b : b;
    b = i % a[3] == 0 ? 1-b : b;
    k += b;
  }
  cout << "otvet " << k;
}

[Вячеслав]

При исходном массиве из 4 элементов возможно 24 варианта его перестановки.
Верный ответ на массиве 2 6 8 3 формула дает в следующих вариантах:
3682 6382 2386 3628 6328 2368 2638 2683 Всего 8 из 24
На массиве 2 4 8 16:
4 8 16 2 - 2 8 16 4 - 4 2 16 8 - 2 4 16 8 - 4 8 2 16 - 2 8 4 16 - 4 2 8 16 - 2 4 8 16
Тоже 8 верных расстановок.
А вот на массиве 2 3 5 7 - вообще ни одного верного ответа. Более того 2 3 5 уже ни одного верного ответа по формуле. На массиве 2 3 - обе расстановки дают верный результат по формуле.

Что-то должно быть еще, наверное. Зацепила меня эта задача. Может посоветуете сообщество где можно поспрашивать людей ?