|
Действия ...
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
13.02.2016, 01:19
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Здарова челы! Сори за боян и олимпиаду. В смежном топике ботаны увлеклись сравнением чисел астрономической разрядности (дай бох им всем здоровья) а мы тут будем колбасить теплые "ламповые операции". OK! Let is go! Задача. http://acmp.ru/index.asp?main=task&id_task=337 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 02:14
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
mayton, но ведь суббота! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 02:32
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
В принципе решается тупым перебором, но вот уложится ли он в 2 секунды - не уверен. Точнее, при фактических входных данных, конечно, уложится, а вот при количестве лампочек ближе к 10 9 - уже вряд ли. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 07:22
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Считаем от 1 до N, каждый шаг проверяем на какое количество P i делится нацело. Если нечетное "итого+1" дальше оптимизация: разложение на простые, поиск минимального шага цикла, поиск одинаковых интервалов и т.д. и т.п. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 07:30
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
НОД(P) это шаг цикла НОК(P) предел цикла, дальше он повторяется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 07:35
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
В массиве P много повторов (100 элементов <50). Все задвоения надо просто выкинуть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 09:03
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Чтобы не делить, проще использовать К счетчиков каждый со своим шагом Р: нашли минимум, посчитали кол-во счетчиков равных минимуму, нечетное - "итого+1", каждый счетчик в минимуме увеличить на Р и т.д. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 13:36
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Пока есть мысль что некоторые кратные инверсии типа 2:4 можно соптимизировать и учесть заранее. Два на четыре это тоже самое что четыре но со "сдвигом". Есть также мысль проверять взаимную простоту чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 17:30
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Входные данные 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 . . . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 18:16
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
maytonБиткарта? Точно. Забыл выкинуть лишнее. Поправил =) Time elapsed: 00:00:00.6150498 Lamps = 525373291. Press any key to continue . . . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 18:18
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
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 Вообще некогда, попозже, если успею - напишу. Но вроде все очень просто. Я основные детали алгоритма выше уже изложил. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 18:45
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Про шаг 1 наврал, надо считать без него, а потом инверсия "итого = всего - итого" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 19:02
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Dima Tmayton, для биткарты 16 Мб не хватит. PS Вообще некогда, попозже, если успею - напишу. Но вроде все очень просто. Я основные детали алгоритма выше уже изложил. Думаю что в этом весь цимес. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 19:16
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Да, цимес имеется. У меня на сайтике стабильно заваливается 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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 20:23
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
SiemarglУ меня на сайтике стабильно заваливается 7й тест Написал. так же 7. Wrong answer. Есть какая-то комбинация в условиях которую не учли. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 20:36
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
SiemarglПереписывать на С++ не хочу. на C# используй структуры (struct вместо class), будет близко по скорости к c++ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 20:38
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Dima TSiemarglПереписывать на С++ не хочу. на C# используй структуры (struct вместо class), будет близко по скорости к c++ а есть, вообще, готовый пример, показывающий что сортировка структур идет быстрее сортировки классов? Или это религиозная догма. Пытался както померять скорость на структурах и на классах - разницы не увидел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 20:45
|
|||
|---|---|---|---|
|
|||
Тяпничные лампочки |
|||
|
#18+
Dima TSiemarglУ меня на сайтике стабильно заваливается 7й тест Написал. так же 7. Wrong answer. Есть какая-то комбинация в условиях которую не учли. Например, число в данных встречается дважды. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 20:46
|
|||
|---|---|---|---|
|
|||
Тяпничные лампочки |
|||
|
#18+
Dima TЕсть какая-то комбинация в условиях которую не учли. Попробуйте такое: Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 21:00
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Dimitry SibiryakovDima TЕсть какая-то комбинация в условиях которую не учли. Попробуйте такое: Код: plaintext 1. спасибо, все банально тупо переполнение при расчете НОК, выход за разрядность ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 21:10
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Dimitry SibiryakovDima TЕсть какая-то комбинация в условиях которую не учли. Попробуйте такое: Код: plaintext 1. Переполнение убрал, но теперь "Time limit exceeded", надо еще какую-то оптимизацию дополнительную. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 21:13
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Можно попробовать окна из биткарт, как тут делал ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.02.2016, 22:44
|
|||
|---|---|---|---|
Тяпничные лампочки |
|||
|
#18+
Все гораздо хуже. Я пока сходил за пивом, изобрел решение без биткарт, без массивов и вообще без сложностей. Все= в 2с не укладывается этот шарп ( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&tablet=1&tid=1340780]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
142ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
43ms |
get tp. blocked users: |
1ms |
| others: | 225ms |
| total: | 450ms |
| 0 / 0 |
