Как решить задачу?

Question

[BitNeBolt]

Задача

Моё решение:

n = int(input())
 
elems = set()
 
for i in range(0, 22):
    for j in range(0, 22):
        for k in range(0, 22):
            elems.add(2 ** i * 3 ** j * 5 ** k)
 
elems = sorted(elems)        
print(elems[n-1])

Для первых тестов работает нормально, простых чисел и кратных им (кроме 2, 3 и 5) вроде не выдает (просматривал вручную некоторые).

Что не так? В чем суть задачи?

Answer 1

[Wataru]

Вы правильно поняли, какого вида числа будут в последовательности (перемноженные степени 2, 3 и 5).

Проблема в том, что вы, например, пропустите число 2^23, которое входит в первые 10000.

Вам надо поднимать границы от 22, пока сгенерированная последовательность (первые 10000 чисел) не перестанет менятся. Вы сгенерируете первые 10000 чисел точно, и какие-то дальше в последовательности (возможно с пропусками) - всего будет сильно больше 10000 чисел.

Но скорее всего, придется поменять алгоритм. Поскольку ограничения маленькие, то тут можно делать что-то типа BFS. Вы вычисляйте числа в последовательности по порядку. И поддерживайте множество возможных следующих чисел. Каждый раз дописывайте минимальное число из кандидатов к последовательности и добавляйте к кандидатам это новое число, умноженное на 2, на 3 или на 5. Это будет квадратичный алгоритм. Можно использовать heap или какой-нибудь set, тогда будет за O(n log n).

Еще есть линейный алгоритм. Он получается из предыдущего так: все кандидаты разбейте на 3 множества - те, которые получены домножением на 2, на 3 и на 5. Каждое такое множество в итоге будет тупо сама же последовательность, домноженная на 2, 3 или 5. Поэтому единственное, что вам надо знать для полного описания кандидатов - это какое число из последовательности было домножено на 2,3 или 5. Это три индекса.

Т.е. решение будет поддерживать три индекса в уже сгенерированном массиве. Потом смотреть, какое число, домноженное на соответсвующий множитель минимально, это число дописывать в последовательность и этот индекс сдвигать на 1.

Answer 2

[BorLaze]

Ты неправильно генеришь данные.

Смотри:
1 шаг: в массиве только [1] (число 1 является элементом последовательности)
2 шаг: берем 1, добавляем 2, 3, 5 (если a – элемент последовательности, то 2a, 3a, 5a тоже являются элементами последовательности) - а равно 1, в итоге получаем [1, 2, 3, 5]
3 шаг: берем 2, добавляем 2*2, 3*2, 5*2 (а теперь равно второму элементу, 2), сортируем: [1, 2, 3, 4, 5, 6, 10]
4 шаг: берем 3... ну, и так далее.

Comments

[BitNeBolt]

Суть получается в том, что числа последовательности являются произведениями степеней 2, 3 и 5. Ранее было отвечено, что моя программа генерирует числа, но не первые 10000 последовательности, а просто числа из неё.

Ваш вариант должен решить эту проблему, так как выполняется сортировка, но из-за неё же, мне кажется, он будет выполняться слишком долго. Вместо сортировки я буду использовать очередь с приоритетом, анализируя наименьший элемент. Почти как в бфс, только берется ближайший сосед.

[longclaps]

мне кажется, он будет выполняться слишком долго

BitNeBolt, когда кажется - крестятся. Твой вариант выливается в сортировку кучей, что, разумеется, медленнее встроеной сортировки. Подумай над этим.

N, l = 3 * 10 ** 17, [1]  # N подобрано вручную 
while l[-1] * 2 < N:
    l.append(l[-1] * 2)
for p in 3, 5:
    t = l
    while t:
        l += (t := [a for a in (b * p for b in t) if a < N])
l.sort()
for i in 2, 9, 10000:
    print(i, l[i - 1])

[BitNeBolt]

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

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

[longclaps]

...выглядит для меня загадочным

пардон

N, l = 3 * 10 ** 17, [1]  # N подобрано вручную
while l[-1] < N:
    l.append(l[-1] * 2)  # просто список со степенями двойки
for p in 3, 5:
    t = l  # используем исходный список как затравку
    while t:  # пока затравка не пустая
        # делаем лист из её элементов, домноженых на p
        # назначаем его новой затравкой
        # и добавляем его к исходному списку
        l += (t := [a for a in (b * p for b in t) if a < N])
        # заметь, в t только элементы кратные p**i, в l таких не было и set() не нужен
l.sort()  # 
for i in 2, 9, 10000:  #
    print(i, l[i - 1])

[BitNeBolt]

longclaps, спасибо