Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.05.2015, 11:36   #11
Demius
Пользователь
 
Регистрация: 03.12.2012
Сообщений: 24
По умолчанию

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

Последний раз редактировалось Demius; 03.05.2015 в 11:45.
Demius вне форума Ответить с цитированием
Старый 05.05.2015, 13:09   #12
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Код:
{
 Ибо  не совсем понятен момент с единицей (что за "или" в условии?),
 буду решать задачу так : чтобы перекрасить все числа кратные K,
 нужно указать K. Чтобы перекрасить все простые числа, нужно скормить 0.
 Чтобы перекрасить одну лишь единичку, нужно ввести 1
}
.....
так там в условии всё просто.
если K ЛЮБОЕ число (больше единицы), то красятся те элементы, номер которых кратен K
если K единица, тогда красятся элементы, индексы которых ПРОСТЫЕ числа и при этом красится элемент с индексом 1.
ну, тут сделано такое допущение, что в данном случае множество простых чисел формально расширено и включает единицу.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 05.05.2015, 13:15   #13
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
ну, тут сделано такое допущение, что в данном случае множество простых чисел формально расширено и включает единицу.
Фи.. Ну поправить, думаю, не составит труда
Poma][a вне форума Ответить с цитированием
Старый 05.05.2015, 13:31   #14
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

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

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

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


а вообще, Вы, Poma][a, большая умница!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 05.05.2015, 13:41   #15
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

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

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

Цитата:
а вообще, Вы, Poma][a, большая умница!
не нашел смайлика с надписью "ну что Вы!"
Poma][a вне форума Ответить с цитированием
Старый 05.05.2015, 13:55   #16
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

всё ясно. спасибо.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 05.05.2015, 18:58   #17
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

Хотел просто +1, но что-то весы предложили мне порадовать кого-нибудь другого...
Присоединяюсь к
Цитата:
а вообще, Вы, Poma][a, большая умница!
FPaul вне форума Ответить с цитированием
Старый 11.05.2015, 16:16   #18
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

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

Если есть идеи по оптимизации - милости просим
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Очень сложная задача про векторы logikal Помощь студентам 4 29.04.2014 22:29
Delphi - Очень простая задача! honest Помощь студентам 1 11.06.2009 14:10
Не простая, но очень интересная задача (Pascal)! Juliya_U Паскаль, Turbo Pascal, PascalABC.NET 29 17.04.2009 19:33