Помогите решить задачу "Лампочки"!

Имеется следующая задачка:

Имеется ряд из N лампочек, которые пронумерованы от 1 до N. Изначально ни одна из лампочек не горит. Далее происходит K последовательных линейных инверсий этого ряда ламп. Под линейной инверсией понимается инверсия каждой P-й лампочки в ряде. Например, если P=3, то произойдет инверсия 3й, 6й, 9й и т.д. лампочек.

Требуется определить: сколько горящих лампочек останется после реализации всех заданных линейных инверсий?

Входные данные

В первой строке входного файла INPUT.TXT заданны числа N и K – число лампочек и число линейных инверсий. Вторая строка состоит из K целых чисел Pi, задающих период данных инверсий. (1 <= N <= 10^9, 1<=K<=100, 1 <= Pi <= 50)


Выходные данные

В выходной файл OUTPUT.TXT следует вывести ответ на задачу.

У кого какие мысли пишите!!!!

Как говорил препод у нас в инсте - "Ну, чтобы до сердца дошло - пример". Пример - ...отсутствует. Посему буду считать что условие понял верно.
Пишем алгоритм:

Есть массив - А, размер 10^9 (зависит от N), инициализируем нулями (положение выкл)
Есть масиив - Б, размер 100 (зависит от K)

Считываем данные, заполняем массив Б (элементами Pi).

Обработка происходит в двойном цикле. Внешний цикл - от 0 до K, шаг 1; внутренний от 0 до N, шаг Б[K].
В теле цикла инвертируем значение А[счетчик внутреннего цикла].

Усе.

Ну это тупой вариант, как грится - в лоб.
Если похитрее - для начала можно обработать массив Б. Если в нем встречаются два одинаковых значения(в условии не сказано, что такого не может быть) то их можно "сократить".

Очевидные вещи (навскидку):
- Лампа горит, если количество "инверсий" нечетно;
- Парные инверсии можно отбросить;
- Период конечного состояния = НОК(Р).

Из любопытства посчитал - масимально возможный период = 619808900849199341280

PS. Обработка массива из 10^9 элементов (даже битовых) - это, я вам скажу... однако поскольку количество элементов намного меньше максимального периода - задачка сильно смахивает на переборную.

Сообщение отредактировано: Akina - 23.09.08, 15:20

Суровые условия.

Слишком большое N не позволяет решить задачу "в лоб" (для хранения всего ряда потребуется около 120 МБ памяти). Слишком большое K затрудняет использование методов вроде "выбрать все числа, делящиеся на P или Q, но не на P и Q одновременно" (слишком много таких условий, легко запутаться). Большой диапазон P не позволяет (в общем случае) выделить наименьшее общее кратное и разбить ряд на меньшие периоды (это самое НОК намного больше N).

Я сталкивался с похожей проблемой при построении бесконечного (точнее, очень длинного) ряда простых чисел методом "решето Эратосфена". Решение заключается в том, чтобы разбить длинный ряд на короткие блоки, обрабатывать каждый блок отдельно, и для каждого числа P[i] запоминать номер первого элемента в следующем блоке, который нужно будет инвертировать. Когда очередной блок обработан (применены все инверсии), считаем количество включенных элементов и добавляем его к общей сумме.

Пусть мы разбили ряд на блоки длиной M элементов (M невелико), блоки и элементы в блоке нумеруются с единицы. Для каждого числа P[i] и для каждого блока определен номер первого инвертируемого элемента - S[i, j], где j - номер блока. S[i, 1] = P[i], S[i, j] = P[i] - (M - S[i, j-1]) mod P[i], где mod - остаток от целочисленного деления. Изначально все элементы в блоке выключены. Для каждого числа P[i] инвертируем каждый P[i]-ый элемент, начиная с S[i, j]-ого, и вычисляем следующее значение S. Когда все инверсии для всех P[i] сделаны, считаем включенные элементы и переходим к следующему блоку.

Пример: M = 100, P[i] = 13, S[i, 1] = P[i] = 13. Инвертируем 7 элементов, вычисляем S[i, 2] = P[i] - (M - S[i, 1]) mod P[i] = 13 - (100 - 13) mod 13 = 13 - 9 = 4 (во втором блоке начинаем инверсию с четвертого элемента).

Прежде, чем начинать работу, желательно учесть следующее: если среди P[i] встречается (2*n) одинаковых чисел, конечный эффект будет такой же, как если бы этих чисел вообще не было; если встречается (2*n + 1) одинаковых чисел, эффект такой же, как если бы было только одно такое число.

Блин, свел задачу к уже решенной - как математик из анекдота :( А все решается намного проще и без лишнего расхода памяти.

Перебираем числа L от 1 до N, для каждого P[i] храним "расстояние" до следующего кратного числа (для единицы это "расстояние" равно P[i] - 1). При переходе к следующему L уменьшаем эти "расстояния" на единицу. Если для какого-то P[i] "расстояние" уменьшилось до 0 - помечаем L как кратное P[i] и в "расстояние" записываем P[i]. Считаем количество P[i], для которых L является кратным. Если это количество нечетное - лампочка горит, если четное - не горит.

Цитата AVA12 @ 23.09.08, 17:14

Перебираем числа L от 1 до N

То есть полный перебор.

Хм, действительно перебор какой-то (или я алгоритм не понял )... Но как-то это слишком медленно получается если нам требуется число действий пропорциональное N.

На самом деле проще посчитать так:
Берем первое число P₁, тогда после применения будут гореть N/P₁ лампочек (тут и далее подразумевается округление вниз).
Берем второе число P₂, после второй инверсии будут гореть N/P₁ + N/P₂ - N/НОК(P₁, P₂) * 2 ламочек (поясню, мы считаем сколько зажигает лампочек каждая инверсия поотдельности и вычитаем из них кол-во лампочек, зажженных обоими).
Для трех инверсий: N/P₁ + N/P₂ + N/P₃ - N/НОК(P₁, P₂) * 2 - N/НОК(P₁, P₃) * 2 - N/НОК(P₂, P₃) * 2 + N/НОК(P₁, P₂, P₃) * 4.
И так далее. По индукции всё получается довольно просто.

Вот только при наивном подходе у нас в сумме будет 2^K слагаемых, что, вообще говоря, отрицательно сказывается на производительности. Но функция НОК растет довольно быстро (хоть у нее и более одного аргумента, но, думаю, понято, что я имею ввиду), и поэтому большинство слагаемых будут равны нулю! Поэтому применяем идею: как только HOK(...) превышает N, то это слагаемое и все последующие в которых учавствуют теже аргуменеты (+плюс какие-то другие) можно не считать.
Осталось научится быстро определять такие нулевые слагаемые.
Для этого заводим отображение M: p -> i, где p - инверсия, i - коэффициент перед слагаемым в сумме.
Изначально M пусто, и для каждого k (1 <= k <= K) добавляем в M пару (P_k -> 1) и обновляем отображения для всех элементов M - то есть добаляем пару (НОК(P_k, p_j) -> -2*i_j), где (p_j -> i_j) - уже существующая пара в M.

Пример, если у нас N=100, и на вход пришли числа 3, 4, 5, 8 то M будет эволюционировать так:
k = 0:

p	i

k = 1:

p	i
3	1

k = 2:

p	i
3	1
4	1
12	-2

k = 3:

p	i
3	1
4	1
12	-2
5	1
15	-2
20	-2
60	4

k = 4:

p	i
3	1
4	1
12	-2
5	1
15	-2
20	-2
60	4
8	-1
24	2
40	2
120	-

120 не вошло в M, т.к. N < 120

Все, теперь, когда у нас M построено, то кол-во лампочек считается элементарно:
Sum_{k \in M}( (N / p_k) * i_k)


Работает довольно быстро (при тупой реализации в худшем случае - одна десятая секунды), памяти практически не нужно (ну пара сотен килобайт - максимум) (лень сейчас получать оценки сложности, кому интересно - посчитайте).
Единственно, очевидную оптимизации в виде удаления пар одинаковых чисел на входе лучше тоже сделать, хотя и без нее не сильно медленее получается.

Цитата albom @ 23.09.08, 19:42

Работает довольно быстро

Если не считать, что количество групп НОКов = 2^k-1... если останется полсотни периодов, то лучше прямой перебор

Цитата Akina @ 23.09.08, 20:41

Если не считать, что количество групп НОКов = 2^k-1...

Пост мой весь прочитал или нет?
Да, всего групп 2^K, но почти все они нулевые и мы их умеем эффективно отсекать.

Цитата Akina @ 23.09.08, 20:41

если останется полсотни периодов, то лучше прямой перебор

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

А трудоемкость подсчета 2^k НОКов ?
Они не нулевые, а больше N, но их же надо посчитать??

Да уж, помоему ( ) все приведённые варианты имеют большую трудоемкость, чем прямой перебор. Вижу вариант в упрощении массива чмсел Pi. Кстати, по условию K < 100, но Pi < 50. Так что если K будет больше 50, значит будут повторения, которые сократяться. Можно дальше упрощать. Скажем, преобразовать массив Рi в матрицу. Где первое значение это шаг, а второе это сдвиг. Таким образом пара чисел у которых НОД равен одному числу, сократятся до одного числа, а сдвиг потом будет учтен по расчете.

Цитата _lcf_ @ 23.09.08, 21:30

Они не нулевые, а больше N, но их же надо посчитать??

Да не нужно их считать! Прямо же написал и даже выделил курсивом Идею При ее применении НОКи мрут как мухи

Цитата _lcf_ @ 23.09.08, 21:30

все приведённые варианты имеют большую трудоемкость, чем прямой перебор.

Ты не прав

Добавлено 23.09.08, 21:39
Вот тебе числа при N=10^9, K=50, числа P_i разные:
количество посчитаных НОК от общего числа: 0.0000000256%
максимальный размер таблицы M: 38k элементов

albom может объяснишь попроще, как отображение М помогает искать НОКи большие N...

Цитата _lcf_ @ 23.09.08, 21:49

как отображение М помогает искать НОКи большие N...

Нам не нужны НОКи больше N, так как они не дадут вклада в ответ (первая загоревшаяся лампочка при такой комбинации отстоит от начала на расстояние больше чем N).

Ваще не берусь никак судить.
С отображением я все понял. Дальше:

Цитата albom @ 23.09.08, 21:32

количество посчитаных НОК от общего числа: 0.0000000256%
максимальный размер таблицы M: 38k элементов

Я бы сказал имеено так - посчитано 38 тыщ НОКов. Модуль 10^9. Какая таки трудоемкость? Или ты знаешь какой-то хитрый способ поиска НОКов?

Добавлено 23.09.08, 22:30
здесь была чушь

Сообщение отредактировано: _lcf_ - 23.09.08, 22:33

Цитата _lcf_ @ 23.09.08, 22:23

Я бы сказал имеено так - посчитано 38 тыщ НОКов.

38k - размер таблицы M, НОКов счиатается больше, так как они довольно часто совпадают, и из них примерно каждый четвертый посчитаный НОК не попадает в таблицу, т.к. оказывается больше N.

Цитата _lcf_ @ 23.09.08, 22:23

Какая таки трудоемкость? Или ты знаешь какой-то хитрый способ поиска НОКов?

Трудоемкость поиска НОК? Ну первый аргумент у НОК всегда число P_i, так что можно сделать препроцессинг и считать весьма быстро, хотя достаточно считать просто НОК(a,b) = a * b / НОД(a, b), а НОД уже обычным алгоритмом Евклида.

Цитата albom @ 23.09.08, 21:32

максимальный размер таблицы M: 38k элементов

это после отбрасывания бОльших чем 10^9? без отбрасывания у меня получилось 442367 НОКов.

Добавлено 24.09.08, 05:36

Цитата albom @ 23.09.08, 20:55

Пост мой весь прочитал или нет?
Да, всего групп 2^K, но почти все они нулевые и мы их умеем эффективно отсекать.

Да... отсекать умеем... но ОБРАБОТАТЬ это придется. И что считать 2^K групп, что отсекать их - имхо один хрен

Цитата Akina @ 24.09.08, 05:10

но ОБРАБОТАТЬ это придется.

Нет, зачем нам их обрабатывать?
Я уже написал результат эксперемента, какой процент достаточно обрабатывать.

Цитата Akina @ 24.09.08, 05:10

это после отбрасывания бОльших чем 10^9? без отбрасывания у меня получилось 442367 НОКов.

В M находятся только пары у которых p не больше N.

Цитата AVA12 @ 23.09.08, 17:14

Блин, свел задачу к уже решенной - как математик из анекдота А все решается намного проще и без лишнего расхода памяти.

Перебираем числа L от 1 до N, для каждого P[i] храним "расстояние" до следующего кратного числа (для единицы это "расстояние" равно P[i] - 1). При переходе к следующему L уменьшаем эти "расстояния" на единицу. Если для какого-то P[i] "расстояние" уменьшилось до 0 - помечаем L как кратное P[i] и в "расстояние" записываем P[i]. Считаем количество P[i], для которых L является кратным. Если это количество нечетное - лампочка горит, если четное - не горит.

Попробовал - работает в 9 раз медленнее, чем предложенный тобой ранее вариант в разбиением на блоки

Я разбивал на блоки по 1000 лампочек.

Самое главное то забыл написать, что время на тест 1 сек.
а так кому интересно вот ссылка на эту задачу: http://acmp.ru/index.asp?main=task&id_task=337

Похвастаюсь, что-ли
Задача принята, правда скорость конечно не очень (если интересно, расскажу как еще раза в три можно ускорить ), да и памяти почему-то съела аж 3 мегабайта (спишем это на кривость stl и моего кода)...

А ваши алгоритмы какой результат дают? Сравнимся?
Прикреплённый файлlights.zip (0.76 Кбайт, скачиваний: 749)

Цитата igor9669 @ 24.09.08, 16:33

время на тест 1 сек

Следовательно, все-таки генерация массива НОДов.

Цитата Akina @ 24.09.08, 17:06

Цитата igor9669 @ 24.09.08, 16:33

время на тест 1 сек

Следовательно, все-таки генерация массива НОДов.

Массив НОДов? Это о чем?

В любом случае не ясно, как связан текст цитаты ( про одну секунду) и твое заключение.

Цитата albom @ 24.09.08, 17:05

А ваши алгоритмы какой результат дают?

Моя реализация алгоритма с разбиением на блоки на компьютере, эквивалентном на таких задачах p4-1700 работает 0.8 сек при N = 10^6 - для N = 10^9 будет соответственно 800 сек

Цитата albom @ 24.09.08, 17:11

Массив НОДов? Это о чем?

Наверное, он имел в виду массив пар (НОК,коэффициент), т.е. твой алгоритм.

Сообщение отредактировано: Bug Hunter - 24.09.08, 17:37

Цитата Bug Hunter @ 24.09.08, 17:33

Наверное, он имел в виду массив пар (НОК,коэффициент), т.е. твой алгоритм.

Может быть, тем не менее связь между посылкой и следствием утверждения остается неясной

Цитата albom @ 24.09.08, 17:42

Может быть, тем не менее связь между посылкой и следствием утверждения остается неясной

Совершенно понятно, что имелось в виду, что требуемую скорость может дать только твой алгоритм.

На похвалу напрашиваешься?

Что мой алгоритм даст требуемую скорость я и так знаю. Но мне не очевидно, что Akina под этим имел именно мой алгоритм. Если у него есть какая-то отличная идея, хорошо бы ее услышать.

albom, не заедайся это очепятка, и есссно речь о НОКах.

Цитата albom @ 23.09.08, 19:42

Хм, действительно перебор какой-то (или я алгоритм не понял )... Но как-то это слишком медленно получается если нам требуется число действий пропорциональное N.

На самом деле проще посчитать так:

а можно ее на паскале решить? когда находим n div nok(p[1],p[2]) надо умножать на степень двойки или каждый раз увеличивать на 2?

Цитата OnaceH @ 24.10.08, 18:24

а можно ее на паскале решить?

Можно

Цитата OnaceH @ 24.10.08, 18:24

когда находим n div nok(p[1],p[2]) надо умножать на степень двойки или каждый раз увеличивать на 2?

Не понял, когда это мы тут считаем "n div nok(p[1],p[2])"?

Но, в любом случае, на 2 в своем решении я вроде ничего явно не увеличивал...


[offtopic]
Эх, судя по тому, как резко увеличилось в системе количество успешно сданных решений с очень похожими параметрами, что-то мне кажется, что некоторое просто берут исходник и сдают его, практически ничего не меняя. Печально, если это так...
[/offtopic]

Цитата albom @ 24.10.08, 18:40

Цитата OnaceH @ 24.10.08, 18:24

когда находим n div nok(p[1],p[2]) надо умножать на степень двойки или каждый раз увеличивать на 2?

Не понял, когда это мы тут считаем "n div nok(p[1],p[2])"?

вот здесь вы писали: N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4
где умножаете на 2, потом на 4, там 2 в степени 1, потом 2 и т.д?

да

Я не как не могу понять что в файле написано, т.к. не знаю C++. можете хотя бы алгритм в математическом виде написать?

Идею я уже рассказал, что не ясно?

Цитата albom @ 30.10.08, 15:32

Идею я уже рассказал, что не ясно?

я не понимаю отображение М, что это и еще что за стрелочки стоят, где р->i. Вот это я не совсем понимаю

В табличке:
p - это НОК;
i - коэффициенты при НОК.

Albom
Извини но твй фыйл в архивк ничем не распознаётся
Он формата bgp чем такое открыть

Ищи косяк у себя, этот исходник уже человек 10 успешно сдали

А лучше напиши программу сам - будет больше пользы

Цитата albom @ 16.11.08, 19:14

Ищи косяк у себя, этот исходник уже человек 10 успешно сдали

А лучше напиши программу сам - будет больше пользы

Пробовал не прет
Если не жалко кинь на
Slava_1_9_9_2@mail.ru txt файлом

Пробовал не прет
Если не жалко кинь на
Slava_1_9_9_2@mail.ru txt файлом

Лучше рассказывай как пробовал, что не получилось?

Цитата albom @ 17.11.08, 09:34

Лучше рассказывай как пробовал, что не получилось?

Слишком много НОК-ов получается(или я непонял идею ). В массив невмешается. Что делать?

Как ты хранишь их сейчас? Когда начинают "невмещаться"?

Цитата albom @ 18.11.08, 18:21

Как ты хранишь их сейчас? Когда начинают "невмещаться"?

В моей программе при k=10 длина массива получаеться 1023( ). а при 100 невмещаеться

Повторю вопрос, Как ты хранишь их сейчас?
Без этого рассуждения о том, что при k=10 работает, а при k=100 уже нет, ничего не дадут.

Цитата albom @ 19.11.08, 04:06

Повторю вопрос, Как ты хранишь их сейчас?
Без этого рассуждения о том, что при k=10 работает, а при k=100 уже нет, ничего не дадут.

Храню в массиве типа longint и длиной 100000000

Как тогда заполняешь этот массив?
И не скупись на подробности. Ты вообще заинтересован в решении задачи или нет? Мне из тебя информацию по кусочкам тянуть как-то совсем не интересно, это же тебе нужно, а не мне. Я так считаю.

Цитата albom @ 19.11.08, 04:15

Как тогда заполняешь этот массив?
И не скупись на подробности. Ты вообще заинтересован в решении задачи или нет? Мне из тебя информацию по кусочкам тянуть как-то совсем не интересно, это же тебе нужно, а не мне. Я так считаю.

Например для К=4 и Р=3,4,5,6 будет
k=1;
p=3;
k=2;
p=3,4,12;
k=3;
p=3,4,12,5,15,20,60;(60=nok(20,12))
k=4;
p=3,4,12,5,15,20,60,6,12,12,30,30,60,60,12,12,12,60,60,... и т.д.
т.е. для каждого p[k] вычисляю нок(p[k],p[i]) где i->1 и добавляю с конца

Цитата SOGES @ 19.11.08, 04:27

p=3,4,12,5,15,20,60,6,12,12,30,30,60,60,12,12,12,60,60,... и т.д.

Я конечно понимаю, что на примере можно что-то показать, но мне не понятно откуда берутся эти числа.
Вот почему, например, часть 60,6,12 выглядит не как 60,6,6,12, или откуда берется зеленая последовательность, и какой тут может быть "и т.д.", если исходных чисел только 4?
Но в любом случае, без знаний как (по какому правилу) ты заполняешь этот массив, конструктивно можно сказать пока только одно: повторяющихся ключей в нем быть не должно.

Цитата albom @ 19.11.08, 04:39

Цитата SOGES @ 19.11.08, 04:27

p=3,4,12,5,15,20,60,6,12,12,30,30,60,60,12,12,12,60,60,... и т.д.

Я конечно понимаю, что на примере можно что-то показать, но мне не понятно откуда берутся эти числа.
Вот почему, например, часть 60,6,12 выглядит не как 60,6,6,12, или откуда берется зеленая последовательность, и какой тут может быть "и т.д.", если исходных чисел только 4?
Но в любом случае, без знаний как (по какому правилу) ты заполняешь этот массив, конструктивно можно сказать пока только одно: повторяющихся ключей в нем быть не должно.

Можеш показать как будет изменяться будет p, при К=4 и Р=3,4,5,6

Добавлено 19.11.08, 05:18
Аллоо Albom ты здесь?

k = 1:

p	i
3	1

k = 2:

p	i
3	1
4	1
12	-2

k = 3:

p	i
3	1
4	1
5	1
12	-2
15	-2
20	-2
60	4

k = 4:

p	i
3	1
4	1
5	1
6	-1
15	-2
20	-2
30	2

Cчитаем, что N >= 60

Как ты заполняешь массив?

Вот > так <

Цитата albom @ 19.11.08, 05:26

Вот > так <

Обьясни идею(плиз)

По ссылке уже объяснил как сумел. Второй раз повторяться не интересно. Задавай вопросы по сути.

Цитата albom @ 23.09.08, 19:42

k = 4:

p	i
3	1
4	1
12	-2
5	1
15	-2
20	-2
60	4
8	-1
24	2
40	2
120	-

120 не вошло в M, т.к. N < 120

разве для К=4 вот так небудет?
k = 4:
Р=3,4,12,5,15,20,60,8,24,8,24,40

Объясни, как нужно понимать эту запись?

Цитата albom @ 19.11.08, 06:24

Объясни, как нужно понимать эту запись?

Ну если я правильно понял то для К=4 и Р=3,4,5,8 будет:
3
4
12=Нок(3,4)
5
15=Нок(5,3)
20=Нок(5,4)
60=Нок(5,12)
8
24=Нок(8,3)
8=Нок(8,4)
24=Нок(8,12)
40=Нок(8,5)

И? Что дальше?

Цитата albom @ 19.11.08, 06:35

И? Что дальше?
k = 4:
p i
3 1
4 1
12 -2
5 1
15 -2
20 -2
60 4
8 -1
24 2
40 2
120 -

120 не вошло в M, т.к. N < 120

Если я правильно написал таблицу (Сегодня, 09:33) значит у тебя приведен неправильный пример

Цитата SOGES @ 19.11.08, 06:58

Если я правильно написал таблицу (Сегодня, 09:33)

Не вижу таблицы. У тебя написаны только некоторые тождества в стиле "24=Нок(8,3)", что имеет тот же смысл что и 2+7=9, так как связи с множеством M (а именно из существования такой связи, как я понял, ты хочешь что-то вывести (опять не ясно что же именно)) не прослеживается. Грубо говоря, это пока всего-лишь набор символов, не относящихся к задаче, и что ты ими хочешь показать опять не ясно.

albom
Делаешь вид что типо ничего не понял что другие говорят

В своём решении на первой странице ты рассказал как составить отображение M->i
Но ничего не было сказано о том, как удалять повторяющиеся НОК-и из той таблицы.
Например, при k=4, у тебя в таблицу добавляются всего три пары, когда должно добавляться ещё 8.
те пять пар которые не добавляешь, имеют НОК равный 24, 60, 120 (некоторые по 2 раза).
И потом в таблице ты суммируешь некоторые НОК-и и оттуда получаешь пару (8;-1) (ясно, что без такой оптимизации коэффициент -1 невозможен, как и +2).

Так вот КАК делается поиск одинаковых НОК-ов при добавлении?
Линейный поиск не работает.

исходник lights.zip ужасен.
особенно ужасает строка dst[v]=s, когда v - это какой-то из НОК-ов, НОКи имеют диапазон 1..10^9..

Цитата alex19921992 @ 25.01.09, 08:11

исходник lights.zip ужасен.

Цитата alex19921992 @ 25.01.09, 08:11

особенно ужасает строка dst[v]=s, когда v - это какой-то из НОК-ов, НОКи имеют диапазон 1..10^9..

dst - сбалансированое бинарное дерево. Соответственно, нет ничего ужасного в том, что диапозон возможных ключей (v) есть 1..10^9.

Цитата alex19921992 @ 25.01.09, 08:11

Так вот КАК делается поиск одинаковых НОК-ов при добавлении?
Линейный поиск не работает.

Зависит от того как у тебя устроена таблица.
Один из способов - это представить её в виде бинарного дерева. Можно и хеш-таблицы попробовать.
Далеко не каждое число может быть ключем в M, M получается сильно разреженной и этим надо пользоватся.

Задача просто шикарная. Браво, albom!
Правда, исходник твой не смотрел; попробую сам чего-нибудь наплести.
Но пока идей у меня 0 (zero).

Я вот не понимаю вот эту запись

N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4.

а именно "+ N/НОК(P1, P2, P3) * 4."

если у нас 4 числа,то мы прибавим N/HOK(P1,P2,P3,P4)*8 или что?

объясни плиз чуть подробнее

albom,сори...но я не понял этой формулы...мог бы ты написать чуть понятней?
Плиз!

Блин,кто нить объясните как высчитывать количество лампочек.....на примере больше k=5 инверсий....
а то не понимаю вот эту формулу N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4. для большего количества инверсий((

Что именно не понятно - как по ней считать или откуда она взялась?

да...я не понимаю....как дальше считать...например для четырех инверсий...

Добавлено 29.12.09, 17:13
Вот,Могу сказать как я решал....
я сразу посчитал сумму так S:=s+n div p[i];
затем я отнял все НОКи(дву чисел,каждый с каждым),т.е S:=s-(n div Nok(a,b))*2

а вот в разборе написано N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4.откуда берется +N/НОК(P1,P2,P3)*4 ??? и как дальше считать,если инверсий больше,т.е. именно этот момент не могу понять..

Для 4:
N/P1 + N/P2 + N/P3+N/P4
-N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P1, P4) * 2-N/НОК(P2, P3) * 2 - N/НОК(P2, P4) * 2 - N/НОК(P3, P4) * 2
+N/НОК(P1, P2, P3)*4+N/НОК(P1, P2, P4)*4+N/НОК(P1, P3, P4)*4+N/НОК(P2, P3, P4)*4
-N/HOK(P1, P2, P3, P4)*8

т.е. я правильно понял,если НОК(четное кол-во элементов) то отнимаем иначе слаживаем??? и умножать нужно на 2^(кол-во элементов минус 1)?

Цитата Mr.Traher @ 29.12.09, 17:18

т.е. я правильно понял,если НОК(четное кол-во элементов) то отнимаем иначе слаживаем

спасиб те))буду должен))

Цитата albom @ 23.09.08, 19:42

На самом деле проще посчитать так:
Берем первое число P1, тогда после применения будут гореть N/P1 лампочек (тут и далее подразумевается округление вниз).
Берем второе число P2, после второй инверсии будут гореть N/P1 + N/P2 - N/НОК(P1, P2) * 2 ламочек (поясню, мы считаем сколько зажигает лампочек каждая инверсия поотдельности и вычитаем из них кол-во лампочек, зажженных обоими).
Для трех инверсий: N/P1 + N/P2 + N/P3 - N/НОК(P1, P2) * 2 - N/НОК(P1, P3) * 2 - N/НОК(P2, P3) * 2 + N/НОК(P1, P2, P3) * 4.

Итак разбирался я в вашей формуле и понял, что она не верна.
Предположим: есть 10 лампочек и 2 перестановки 2 и 3
10 2
2 3
По вашей формуле: 10/2+10/3-10*2/6=5+3-3=5
Если смотреть в лоб: от перестановки 2-->5 загорелось; от 3-->+к тем 5 загорелась 3-я и 9-я лампочки, потухла 6. 5+2-1=6 И это верный ответ. Для 2 инверсий формула не верна.

Проверим для 3 инверсий:
Предположим: есть 10 лампочек и 3 перестановки 2,3 и 6
10 3
2 3 6
По вашей формуле: 10/2+10/3+10/6-10*2/6-10*2/6-10*2/6+10*4/6=5+3+1-3-3-3+5=5
Смотрим в лоб: все рассуждения как и для 2 перестановок, но еще загорится 6-я лампочка. 5+2-1+1=7.Итак ответ 7. Для 3 инверсий формула также не верна.
Скажите, пожалуйста, где я не прав?

Добавлено 04.01.11, 00:31

Цитата AdviZzzor @ 04.01.11, 00:23

По вашей формуле: 10/2+10/3+10/6-10*2/6-10*2/6-10*2/6+10*4/6=5+3+1-3-3-3+5=5

Прошу прощения ошибся. 10/2+10/3+10/6-10*2/6-10*2/6-10*2/6+10*4/6=5+3+1-3-3-3+6=6. Но все равно с правильным ответом 7 не сходится.

> По вашей формуле: 10/2+10/3-10*2/6=5+3-3=5

Надо считать буквально как у него:

10/2 + 10/3 - (10/6)*2 = 5 + 3 - 2 = 6

Спасибо, я разобрался.