1

Тема: 178. Задача первая

ограничение времени на тест: 1.5 сек.
ограничение памяти на тест: 16384 KB.
ввод: input.txt
вывод: output.txt


Пусть дано множество простых чисел S={p1...pk}. Рассмотрим те числа, все простые делители которых принадлежат S. Из этих чисел вам требуется найти N-ое по величине (считается, что единица им не принадлежит).

Входные данные
В первой строке входного файла содержится число K (1 <= K <= 1000) и число N (1 <= N <= 1000000). Во второй - последовательность p1...pk.

Выходные данные
Выходной файл должен содержать искомое число.

Пример

Ввод
3 4
2 3 5

Вывод
5

Пояснение
Гарантируется, что ответы на тесты принадлежат диапазону 0..10^18 и все данные простые числа принадлежат отрезку [2..2^31-1].

2

Re: 178. Задача первая

hamming problem
рассматривается, например, в книге Дейкстра "Дисциплина программирования"

3

Re: 178. Задача первая

MBo пишет:

hamming problem
рассматривается, например, в книге Дейкстра "Дисциплина программирования"

Заинтересовался этой задачей, почитал книгу, нашел алгоритм, там используется метод указателей и их сдвигов. Общая сложность получается O(n * k) в тайм лимит не укладывается или же столько операций укладывается в ТЛ?

4

Re: 178. Задача первая

>cложность получается O(n * k)

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

5

Re: 178. Задача первая

MBo пишет:

>cложность получается O(n * k)

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

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

6

Re: 178. Задача первая

>все указатели умножаются
точно ли все?

7

Re: 178. Задача первая

MBo пишет:

>все указатели умножаются
точно ли все?

Не могли бы вы скинуть русскоязычную версию книги, на английском я плохо понимаю, в реализации O(n * k)???

8

Re: 178. Задача первая

http://www.proklondike.com/var/file/dei … g_full.zip
но там вопрос генерализации на k простых (k-smooth numbers) не рассматривается

У Дейкстры после поиска минимума выполняется три оператора do c умножением на соотв. простые.
Фактически же условие в do сработает не для всех веток (возможно, только для одной ветки).

Вот тут кое-что есть
http://linulysses.wordpress.com/2011/06 … alization/
второй цикл for - не с единицы начинается

9

Re: 178. Задача первая

MBo пишет:

Вот тут кое-что есть
http://linulysses.wordpress.com/2011/06 … alization/
второй цикл for - не с единицы начинается

Ссылка у меня не работает.

10 Отредактировано MBo (2011-11-05 19:09:32)

Re: 178. Задача первая

пдф-ка, но на том же сервере
http://linulysses.files.wordpress.com/2 … umbers.pdf
скопирую кусок сюда, но копируется криво

Algorithm 2 Algorithm for Computing H(B)
Initialize queues Q1;Q2; : : : ;Qm to be empty
R =0  ;
for t from 1 to m do
push bt into queue Qt
end for
k  =  0
while k < n do
Let h be the minimum element in the front of each queue Qi (1 <= i <= m)
and assume h принадлежит Qj
for t from j to m do
push h * bt into queue Qt
end for
Remove h from Qj .
Put h into output sequence R
k =   k + 1
end while

11

Re: 178. Задача первая

А где я могу сдать эту задачу? Ссылка приведенная на acm.sgu.ru/olimp не работает.

12

Re: 178. Задача первая

Сайт доступен только с Саратовских IP.
Прошу прощения, можно более конкретно объяснить реализацию данной задачи?

13 Отредактировано bekzattt (2011-12-01 12:04:25)

Re: 178. Задача первая

логика такая же как и в линейном решете Эратосфена,почитать можно тут e-maxx.ru/algo/prime_sieve_linear

как я понел задачу примерно решается она так  http://pastebin.com/byXSB0v7

,сложность алгоритма будет примерно N * log M (M - это количество чисел в куче , кстати если будет тайм лимит подправьте меня smile это изза излишних чисел в куче которые заведомо больше чем нужное нам,но это думаю исправимо ,сейчас просто времени нет додумывать но логика примерно такая кажется)

14

Re: 178. Задача первая

Спасибо большое, логику в целом понял.

По вашему решению:

Test.1: OK with Time 31 ms
Test.2: OK with Time 15 ms
Test.3: OK with Time 15 ms
Test.4: OK with Time 31 ms
Test.5: OK with Time 15 ms
Test.6: OK with Time 15 ms
Test.7: OK with Time 15 ms
Test.8: OK with Time 15 ms
Test.9: OK with Time 15 ms
Test.10: OK with Time 15 ms
Test.11: OK with Time 15 ms
Test.12: OK with Time 15 ms
Test.13: OK with Time 46 ms
Test.14: ML with Time 156 ms
Test.15: ML with Time 875 ms
Test.16: ML with Time 953 ms
Result - 13/16