Решение задачи "Раскрашивание чисел" с Codeforces

Без пояснения   Просмотров: 15


Вам дана последовательность целых чисел a1,a2,…,an. Вам нужно раскрасить элементы, так чтобы:

Если мы рассмотрим произвольный цвет, то все элементы этого цвета должны делиться на минимальный элемент этого цвета.
Количество использованных цветов было бы минимально возможным.
Например, можно покрасить элементы [40,10,60] в один цвет, так как они все делятся на 10. Каждый из цветов можно использовать произвольное количество раз (в частности, разрешается использовать любой цвет ровно один раз). Элементы, покрашенные в один цвет, не обязаны идти подряд.

Например, если a=[6,2,3,4,12], то нужно использовать два цвета: можно покрасить 6, 3, 12 в первый цвет (6, 3 и 12 делятся на 3), а 2 и 4 во второй цвет (2 и 4 делятся на 2). Например, если a=[10,7,15], то нужно 3 цвета (следует покрасить каждый элемент в отдельный цвет).


Код

#include<bits/stdc++.h>
using namespace std;
int a[105],b[105];
int main()
{
	int n;scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int sum=0;
	for (int i=1;i<=n;i++)
	{
		if(b[i]) continue;
		for (int j=i;j<=n;j++) if(a[j]%a[i]==0) b[j]=1;
		sum++;
	}
	printf("%d\n",sum);
	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться