Решение задачи Непростая покраска с Codeforces

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

Положительное целое число называется составным, если оно представимо в виде произведения двух положительных целых чисел, каждое из которых больше 1. Например, следующие числа составные: 6, 4, 120, 27. Следующие числа составными не являются: 1, 2, 3, 17, 97.

Задана последовательность из n составных чисел a1,a2,…,an.

Алиса хочет выбрать любое целое число m≤11 и покрасить каждый элемент в один из m цветов от 1 до m так, что:

для каждого цвета от 1 до m существует хотя бы один элемент этого цвета;
каждый элемент покрашен и притом ровно в один цвет;
наибольший общий делитель любых двух одноцветных элементов больше 1, то есть gcd(ai,aj)>1 для любой пары индексов i,j, если эти элементы покрашены в одинаковый цвет.
Обратите внимание, что одинаковые элементы могут быть покрашены в разные цвета — просто для каждого индекса от 1 до n надо выбрать один из m цветов.

Алиса уже показала, что если все ai≤1000, то она всегда может решить эту задачу, выбрав некоторое m≤11.

Помогите Алисе найти требуемую покраску элементов. Обратите внимание, что вам не нужно минимизировать или максимизировать количество цветов, достаточно найти решения с любым m от 1 до 11.

Код 

#include <bits/stdc++.h>
#define int long long int
using namespace std;
main() {
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		vector<int> a(n), b(n, -1);
		for(int i = 0; i < n; i++)
            cin >> a[i];
		int j = 2, l = 1;
		while(j <= sqrt(1000)){
		    int k = 0;
			for(int i = 0; i < n; i++){
				if(b[i] == -1){
                    if(a[i] % j == 0){
                        b[i] = l;
                        k++;
                    }
				}
			}
			if(k != 0)l++;
                j++;
		}
		cout << l - 1 <<endl;
		for(int i = 0;i < n; i++)
            cout << b[i] << " ";
        cout<<endl;
	}
	return 0;
}

         

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



Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp