0 / 0 / 0
Регистрация: 21.05.2019
Сообщений: 33
1

Непростая покраска

20.04.2020, 14:12. Показов 282. Ответов 0
Метки нет (Все метки)

Положительное целое число называется составным, если оно представимо в виде произведения двух положительных целых чисел, каждое из которых больше 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.

Входные данные
В первой строке записано целое число t (1≤t≤1000) — количество наборов входных данных в тесте. Далее содержатся сами описания наборов.

В первой строке набора записано целое число n (1≤n≤1000) — количество чисел в последовательности a.

Вторая строка набора входных данных содержит n составных целых чисел a1,a2,…,an (4≤ai≤1000).

Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 104.

Выходные данные
Для каждого набора входных данных выведите 2 строки. В первую выведите m (1≤m≤11) — количество использованных цветов. Считайте, что цвета пронумерованы от 1 до m. Во вторую строку выведите любую раскраску элементов, которая удовлетворяет условиям выше. Выведите n целых чисел c1,c2,…,cn (1≤ci≤m), где ci — цвет i-го элемента. Если решений несколько, то выведите любое из них. Обратите внимание, что вам не нужно минимизировать или максимизировать количество цветов, достаточно найти решения с любым m от 1 до 11.

Помните, что каждый цвет от 1 до m должен быть использован хотя бы раз. Любые два одноцветных элемента должны не быть взаимно просты (то есть их НОД должен быть больше 1).

Пример
входные данные
3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961
выходные данные
1
1 1 1
2
2 1
11
4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6

Примечание
В первом наборе входных данных gcd(6,10)=2, gcd(6,15)=3 и gcd(10,15)=5. Таким образом, допустимо раскрасить все три элемента в один цвет. Обратите внимание, что для данного набора входных данных существуют и другие раскраски, которые удовлетворяют требованиям Алисы.

Во втором наборе входных данных в каждый цвет покрашен только один элемент, так что раскраска точно походит под все требования Алисы.

ПОМОГИТЕ ЗДЕЛАТЬ ПОЖАЛУЙСТА!
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.04.2020, 14:12
Ответы с готовыми решениями:

Непростая задачка по массивам
Всем здравствуйте. Впервые на данном форуме, прошу помидорами не закидывать, в случае баяна. ...

Непростая задача на графы.
Здравствуйте! Необходимо решить такую задачу: Антон работает в межгалактическом туристическом...

Одна непростая зaдaчка
Завтра у меня зачет, и мне осталось решить одну задачку, помогите пожалуйста: даны положительные...

Очень непростая программа с класами!
Всем привет! Нужно сделать класс Matrix (квадратная матрица) Действия: -=, *=. Класс должен...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.04.2020, 14:12
Помогаю со студенческими работами здесь

Покраска лабиринта
Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть...

Исчисление сумм и произведений (непростая задачка)
Вычислить и вывести значения соответствующих переменных: L=П (Сверху n, снизу i=3)...

Тип «Клиент» определить как перечисление (enum) со значениями полей «мужчина», «женщина, покраска», «женщина, стрижка»,
Тип «Клиент» определить как перечисление (enum) со значениями полей «мужчина», «женщина, покраска»,...

Покраска градиентом
Нужно покрасить ячеку градиентом в qtablewidget. Когда я просто крашу цветом: QColor color;...

Покраска текста в QPlainTextEdit
Как во время редактирования подсвечивать нужные слова в QPlainTextEdit?

Покраска ячеек в StringGreed
Доброго времени суток. Помогите пожалуйста решить такую задачку... Создать приложение,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru