Простая (или не очень) задача про окраску канареек

[Demius]

Сообщение от Poma][a

Попробовал свой вариант (только решил отказаться от матрицы и считать по строкам)

Poma][a, прогнал ваше решение на нескольких тестах (в т.ч. из обсуждения). Вроде как, всё правильно. Но надо подумать над чем-то эффективнее. Надо оптимизировать решение.

[Serge_Bliznykov]

Сообщение от Poma][a

{
 Ибо  не совсем понятен момент с единицей (что за "или" в условии?),
 буду решать задачу так : чтобы перекрасить все числа кратные K,
 нужно указать K. Чтобы перекрасить все простые числа, нужно скормить 0.
 Чтобы перекрасить одну лишь единичку, нужно ввести 1
}
.....

так там в условии всё просто.
если K ЛЮБОЕ число (больше единицы), то красятся те элементы, номер которых кратен K
если K единица, тогда красятся элементы, индексы которых ПРОСТЫЕ числа и при этом красится элемент с индексом 1.
ну, тут сделано такое допущение, что в данном случае множество простых чисел формально расширено и включает единицу.

[Poma][a]

ну, тут сделано такое допущение, что в данном случае множество простых чисел формально расширено и включает единицу.

Фи.. Ну поправить, думаю, не составит труда

[Serge_Bliznykov]

это да, это можно поправить.

меня другое смущает. там элементов может быть до 10000 и цветов до 1000.
во-первых, ваш алгоритм уже не подойдёт из за ограничений byte и set of ..
а во-вторых, я не проверял, но, мне кажется, перебор очень долго будет происходить...

или я ошибаюсь?


а вообще, Вы, Poma][a, большая умница!

[Poma][a]

там элементов может быть до 10000 и цветов до 1000.
о-первых, ваш алгоритм уже не подойдёт из за ограничений byte и set of ..

Эт да.. Сделано было намеренно.. Нужно было или делать лишнюю работу (бегать по массиву), или писать свое множество, или писать на C++. Т.к. тут были Вы и FPaul (а еще моя лень) - было решено писать на паскале и снизить ограничения. А чтобы это было легко заметить - поставил byte

а во-вторых, я не проверял, но, мне кажется, перебор очень долго будет происходить...

Если Вы уберет слово "очень", то соглашусь. Пусть у нас N канареек и кол-во различных цветов, в которые они раскрашены - K, тогда сложность будет K*N.
K in [1000], N in [10000]. Перемножаем получает 10кк. Если запускать на современном компе, то очень может быть, что за секунду мы уложимся

а вообще, Вы, Poma][a, большая умница!

не нашел смайлика с надписью "ну что Вы!"

[Serge_Bliznykov]

всё ясно. спасибо.

[FPaul]

Хотел просто +1, но что-то весы предложили мне порадовать кого-нибудь другого...
Присоединяюсь к

а вообще, Вы, Poma][a, большая умница!

[Poma][a]

День всем добрый
Тут такое дело. Я оказывается наврал. Сложность будет K*N*N*(logN+sqrt(N))

Если есть идеи по оптимизации - милости просим