Натуральный ряд Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В научно-исследовательском институте, где работает Тимофей, продолжается успешнов…
Натуральный ряд Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В научно-исследовательском институте, где работает Тимофей, продолжается успешнов исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на п-м месте в списке? Формат входных данных Единственная строка входных данных содержит натуральное число п (1 ≤ n < 10°). Формат выходных данных Выведите одно натуральное число - — ответ на вопрос задачи. Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64-битный тип данных, например, long long в C++, int64 в Free Pascal, long Java. Система оценки Решения, верно работающие при 1 ≤ n ≤ 10%, получат не менее 40 баллов. Замечание В примере дано п = 5.
Для решения задачи нам нужно понять, как работа с числовым рядом натуралов (1, 2, 3, ...) будет изменяться после удаления всех четных чисел и затем всех чисел, делящихся на 3.
Сначала из натурального ряда удаляются все четные числа, в результате чего остаются только нечетные числа: 1, 3, 5, 7, 9, ...
Затем мы удаляем все числа, которые делятся на 3 из оставшихся (нечетных) чисел. Это значит, что из списка нечетных чисел мы исключаем числа 3, 9, 15 и так далее.
Теперь нам нужно выяснить, какое число стоит на p-м месте в этом новом последовательности.
Непосредственно можно рассмотреть следующее:
- Нечетные числа: 1, 3, 5, 7, 9, 11, 13, 15, 17, ...
- Из этих чисел мы вычитаем те, которые делятся на 3: 3, 9, 15, ...
Оставшиеся числа: 1, 5, 7, 11, 13, 17, 19, ...
Чтобы найти p-е число в оставшихся, можно использовать программный подход:
- Генерируем нечетные числа.
- Удаляем те, которые делятся на 3.
- Находим p-е число.
Так как p может быть большим (до 10^8), нужно сделать это эффективно.
Вот пример кода на Python, который реализует этот алгоритм:
def find_pth_number(p):
count = 0 # счётчик оставшихся чисел
current_num = 1 # текущее натуральное число для проверки
while True:
# Проверяем, что текущее число нечетное и не делится на 3
if current_num % 2 != 0 and current_num % 3 != 0:
count += 1 # нашли подходящее число
if count == p:
return current_num # это p-ое число
current_num += 1 # переходим к следующему натуральному числу
# Чтение ввода
p = int(input().strip())
# Поиск нужного числа
result = find_pth_number(p)
# Вывод результата
print(result)
Эта программа будет корректно работать для значений p до 10^8 за разумное время. Можно также оптимизировать подход, но это базовая версия решения.
