ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничные лампочки
25 сообщений из 92, страница 1 из 4
  1  все
Тяпничные лампочки
    #39170092
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Здарова челы!

Сори за боян и олимпиаду. В смежном топике ботаны увлеклись сравнением чисел
астрономической разрядности (дай бох им всем здоровья) а мы тут будем колбасить
теплые "ламповые операции". OK! Let is go!

Задача.

http://acmp.ru/index.asp?main=task&id_task=337
...
Рейтинг: 0 / 0
13.02.2016, 01:19
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170106
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

но ведь суббота!
...
Рейтинг: 0 / 0
13.02.2016, 02:14
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170109
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
В принципе решается тупым перебором, но вот уложится ли он в 2 секунды - не уверен.
Точнее, при фактических входных данных, конечно, уложится, а вот при количестве лампочек ближе к 10 9 - уже вряд ли.
...
Рейтинг: 0 / 0
13.02.2016, 02:32
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170149
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Считаем от 1 до N, каждый шаг проверяем на какое количество P i делится нацело. Если нечетное "итого+1"
дальше оптимизация: разложение на простые, поиск минимального шага цикла, поиск одинаковых интервалов и т.д. и т.п.
...
Рейтинг: 0 / 0
13.02.2016, 07:22
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170150
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
НОД(P) это шаг цикла НОК(P) предел цикла, дальше он повторяется.
...
Рейтинг: 0 / 0
13.02.2016, 07:30
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170151
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В массиве P много повторов (100 элементов <50). Все задвоения надо просто выкинуть.
...
Рейтинг: 0 / 0
13.02.2016, 07:35
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170166
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Чтобы не делить, проще использовать К счетчиков каждый со своим шагом Р:
нашли минимум, посчитали кол-во счетчиков равных минимуму, нечетное - "итого+1", каждый счетчик в минимуме увеличить на Р и т.д.
...
Рейтинг: 0 / 0
13.02.2016, 09:03
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170286
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Пока есть мысль что некоторые кратные инверсии типа 2:4 можно соптимизировать
и учесть заранее. Два на четыре это тоже самое что четыре но со "сдвигом".

Есть также мысль проверять взаимную простоту чисел.
...
Рейтинг: 0 / 0
13.02.2016, 13:36
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170373
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Входные данные

nLamps = 1000000000;
nInversions = 10;
Periods = new int[]{19,2,7,13,40,23,16,1,45,9};

Результат
Time elapsed: 00:00:05.2807186
Lamps = 525373291. Press any key to continue . . .
...
Рейтинг: 0 / 0
13.02.2016, 17:30
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Биткарта?
...
Рейтинг: 0 / 0
13.02.2016, 17:47
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170392
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
maytonБиткарта?
Точно. Забыл выкинуть лишнее.
Поправил =)

Time elapsed: 00:00:00.6150498
Lamps = 525373291. Press any key to continue . . .
...
Рейтинг: 0 / 0
13.02.2016, 18:16
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170394
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SiemarglВходные данные

nLamps = 1000000000;
nInversions = 10;
Periods = new int[]{19,2,7,13,40,23,16,1,45,9};

Результат
Time elapsed: 00:00:05.2807186
Lamps = 525373291. Press any key to continue . . .

1. Выкинь единицы. Просто добавь флаг инверсия результата. Т.е. вместо количество нечетных - кол-во четных.

2. Считай до НОК, это примерно 50 млн., дальше все повторяется. Например счетчики 4 и 5: НОК 20, внутри 20 (4,5,8,10,12,15,16, 20) 8 ламп. В миллиарде 8 * 1000000000 / 20 = 400000000. Не забудь что остаток может быть: например НОК = 30, предел 100, т.е. результат = (цикл до 30) * 3 + (цикл до 10).

3. Деление убрал?

mayton, для биткарты 16 Мб не хватит.

PS Вообще некогда, попозже, если успею - напишу. Но вроде все очень просто. Я основные детали алгоритма выше уже изложил.
...
Рейтинг: 0 / 0
13.02.2016, 18:18
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170403
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Про шаг 1 наврал, надо считать без него, а потом инверсия "итого = всего - итого"
...
Рейтинг: 0 / 0
13.02.2016, 18:45
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170409
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tmayton, для биткарты 16 Мб не хватит.

PS Вообще некогда, попозже, если успею - напишу. Но вроде все очень просто. Я основные детали алгоритма выше уже изложил.
Думаю что в этом весь цимес.
...
Рейтинг: 0 / 0
13.02.2016, 19:02
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170416
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Да, цимес имеется.

У меня на сайтике стабильно заваливается 7й тест - если биткарта, то 2с мне нехватает, если без биткарты - то завал по памяти (
Переписывать на С++ не хочу.

В общем с биткартой на данных ниже у меня
nLamps = 1000000000;
nInversions = 10;
Periods = new int[]{19,2,7,13,40,23,16,1,45,9};

Time elapsed work+count: 00:00:01.2806298
...
Рейтинг: 0 / 0
13.02.2016, 19:16
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170440
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SiemarglУ меня на сайтике стабильно заваливается 7й тест
Написал. так же 7. Wrong answer. Есть какая-то комбинация в условиях которую не учли.
...
Рейтинг: 0 / 0
13.02.2016, 20:23
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170447
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SiemarglПереписывать на С++ не хочу.
на C# используй структуры (struct вместо class), будет близко по скорости к c++
...
Рейтинг: 0 / 0
13.02.2016, 20:36
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170448
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
Dima TSiemarglПереписывать на С++ не хочу.
на C# используй структуры (struct вместо class), будет близко по скорости к c++
а есть, вообще, готовый пример, показывающий что сортировка структур идет быстрее сортировки классов? Или это религиозная догма.
Пытался както померять скорость на структурах и на классах - разницы не увидел.
...
Рейтинг: 0 / 0
13.02.2016, 20:38
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170451
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Dima TSiemarglУ меня на сайтике стабильно заваливается 7й тест
Написал. так же 7. Wrong answer. Есть какая-то комбинация в условиях которую не учли.

Например, число в данных встречается дважды.
...
Рейтинг: 0 / 0
13.02.2016, 20:45
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170452
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TЕсть какая-то комбинация в условиях которую не учли.
Попробуйте такое:
Код: plaintext
1.
1000000000 17
2 3 5 7 11 13 17 19 23 29 31 37 39 41 43 47 49
...
Рейтинг: 0 / 0
13.02.2016, 20:46
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170457
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TЕсть какая-то комбинация в условиях которую не учли.
Попробуйте такое:
Код: plaintext
1.
1000000000 17
2 3 5 7 11 13 17 19 23 29 31 37 39 41 43 47 49

спасибо, все банально тупо
переполнение при расчете НОК, выход за разрядность
...
Рейтинг: 0 / 0
13.02.2016, 21:00
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170464
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TЕсть какая-то комбинация в условиях которую не учли.
Попробуйте такое:
Код: plaintext
1.
1000000000 17
2 3 5 7 11 13 17 19 23 29 31 37 39 41 43 47 49

Переполнение убрал, но теперь "Time limit exceeded", надо еще какую-то оптимизацию дополнительную.
...
Рейтинг: 0 / 0
13.02.2016, 21:10
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170466
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно попробовать окна из биткарт, как тут делал
...
Рейтинг: 0 / 0
13.02.2016, 21:13
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170515
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Все гораздо хуже. Я пока сходил за пивом, изобрел решение без биткарт, без массивов и вообще без сложностей.

Все= в 2с не укладывается этот шарп (
...
Рейтинг: 0 / 0
13.02.2016, 22:44
| Ответить | Цитировать | Написать  
Тяпничные лампочки
    #39170521
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Dima TSiemarglПереписывать на С++ не хочу.
на C# используй структуры (struct вместо class), будет близко по скорости к c++
Поучи свою бабушку яичницу жарить =)

У меня уже идеальный алгоритм.
...
Рейтинг: 0 / 0
13.02.2016, 22:59
| Ответить | Цитировать | Написать  
25 сообщений из 92, страница 1 из 4
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничные лампочки
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39170109&tid=1340780]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 153ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 88ms
get tp. blocked users:
 2ms
others: 233ms
total:  520ms
созд. / загр.: 520ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]