Потрiбно побудувати послiдовнiсть a довжиною n, що виконувалися обмеження:
• Для кожного i (1 <= i <= n) l <= ai <= r.
• Для кожного i (1 <= i < n) ai має бути дiльником ai+1.
• Для кожного i (1 <= i < n) ai < ai+1.
Потрiбно знайти максимально можливу довжину послiдовностi.
Формат вхiдних даних
Перший рядок мiстить два цiлi числа l та r (1 <= l <= r <= 10^18).
Формат вихiдних даних
Виведiть одне цiле число — максимально можливу довжину такої послiдовностi.
Приклад
standard input standard output
3 19 3
Примiтка
У прикладi, наприклад, можна мати таку послiдовнiсть [3, 9, 18].
Ответ
5 (1 оценка)
0
mikitaglusko 1 год назад
Светило науки - 13 ответов - 0 раз оказано помощи

Ответ:  Для розв'язання цієї задачі можна скористатися рекурсивним підходом і знайти довжину найбільшої послідовності, що задовольняє умови.

Створюємо функцію, яка приймає параметри: поточне число послідовності, мінімальне та максимальне значення для кожного числа в послідовності, та довжину поточної послідовності. По замовчуванню поточне число - це l, мінімальне та максимальне значення для кожного числа в послідовності дорівнюють l та r відповідно, а довжина поточної послідовності рівна 1.

Визначаємо список дільників поточного числа.

Проходимося циклом по дільникам поточного числа і рекурсивно викликаємо функцію з наступними параметрами: наступне число послідовності - дільник поточного числа, мінімальне значення для наступного числа дорівнює дільнику, а максимальне значення залишається незмінним, та довжина поточної послідовності збільшується на 1.

При кожному рекурсивному виклику функції порівнюємо поточну довжину послідовності з максимальною довжиною, яку ми досі знайшли. Якщо поточна довжина більша за максимальну, то максимальну довжину замінюємо на поточну.

Після циклу повертаємо максимальну довжину, яку ми знайшли.

Оскільки умова l <= ai <= r виконується для кожного числа послідовності, ми можемо змінювати мінімальне та максимальне значення для кожного числа в послідовності відповідно.

Ось реалізація цього підходу на мові Python:

def max_sequence_length(start=l, end=r, prev_num=l, length=1):

   divisors = [d for d in range(prev_num + 1, end + 1) if

Объяснение: Бажаю успіхів у навчанні

Остались вопросы?