Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на п-м месте в списке? Формат входных данных Единственная строка входных данных содержит натуральное число п (1 ≤ n ≤ 10°). Формат выходных данных Выведите одно натуральное число на вопрос задачи. ответ Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64-битный тип данных, например, long long в С++, int64 в Free Pascal, long в Java. Система оценки Решения, верно работающие при 1 ≤ n ≤ 105, получат не менее 40 баллов. Замечание В примере дано п = 5. Из исходного ряда натуральных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... сначала были удалены числа 2, 4, 6, 8,... (как делящиеся на 2). Остался ряд 1, 3, 5, 7, 9, 11, 13, 15, ... Потом из него были удалены числа 3, 9, 15, .. (как делящиеся на 3). Остался ряд 1, 5, 7, 11, 13,.. < ятом месте число 13. Потом из него были удалены числа 3, 9, 15,... (как делящиеся на 3). Остался ряд 1, 5, 7, 11, 13,... На пятом месте число 13. Ввод:5 Вывод:13

Чтобы решить задачу, давайте разберем этапы очистки последовательности натуральных чисел и определим, какое число окажется на позиции \( p \).

1. Исходная последовательность: Начнем с натуральных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

2. Удаление четных чисел: После того как начальник отдела стер все числа, делящиеся на 2, в списке останутся только нечетные числа: \( 1, 3, 5, 7, 9, 11, 13, 15, 17, \ldots \)

3. Удаление чисел, делящихся на 3: Теперь нам нужно удалить числа, делящиеся на 3 из оставшихся. В последовательности нечетных чисел это будут: \( 3, 9, 15, \ldots \) Остальные нечетные числа, которые не делятся на 3, остаются: \( 1, 5, 7, 11, 13, 17, 19, 23, \ldots \)

Теперь, чтобы найти число на позиции \( p \) в этой окончательной последовательности нечетных чисел, мы можем воспользоваться следующим наблюдением:

• Нечетные числа образуют последовательность вида \( 1, 3, 5, 7, 9, 11, 13, \ldots \), где \( n \)-е нечетное число можно найти по формуле: \[ \text{n-ое нечетное число} = 2 \times n - 1 \]

• Затем нужно отфильтровать удаленные из списка числа, делящиеся на 3.

Таким образом, после удаления чисел, делящихся на 3, объём оставшейся последовательности можно вычислить. Если \( p \) - это позиция, которую мы ищем, то число в позиции \( p \) можно найти через отбор нечетных чисел и исключение нечетных чисел, которые делятся на 3.

Реализация алгоритма:

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

Вот подход к решению:

def find_nth_number(n):
    count = 0
    current = 1
    while True:
        if current % 2 != 0 and current % 3 != 0:
            count += 1
            if count == n:
                return current
        current += 1

# Вводим значение n
n = int(input().strip())
print(find_nth_number(n))

Такой алгоритм будет эффективно находить \( n \)-ое оставшееся число, учитывая ограничения задачи.