Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

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

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

Последний раз редактировалось Demius; 03.05.2015 в 12:45.
Demius вне форума   Ответить с цитированием
Старый 05.05.2015, 14:09   #12
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 25,845
Репутация: 5617
По умолчанию

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

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

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

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

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


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

Цитата:
там элементов может быть до 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, 14:55   #16
Serge_Bliznykov
МегаМодератор
СуперМодератор
 
Регистрация: 09.01.2008
Сообщений: 25,845
Репутация: 5617
По умолчанию

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

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

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

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

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

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


19:34.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.