Натхненний легендою про
Вавилонську вежу, Петро вирішив побудувати її аналог у себе в кімнаті. Для
цього він узяв N дитячих будівельних цеглин,
вибрав для себе розмір основи D й висоту вежі Н. Крім того, він вирішив, що розмір кожного наступного рівня
буде відрізнятись від попереднього не більш ніж на одну цеглину. Необхідно
скласти програму, яка визначає, чи можна побудувати вежу за вибраними Петром
параметрами. Якщо можна побудувати таку вежу, то програма повинна видавати,
скільки цеглин повинно бути на кожному рівні.
Ідея розв’язання. Задача є
класичною задачею динамічного програмування. Визначимо, яку максимальну (max) та мінімальну (min)
кількість цеглин потрібно
для побудови вежі з основою D і висотою Н:
(min ≤ N ≤ max) i (Odd(N) = Odd(max) {або Odd(N) = Odd(min)}
Малюнок, який ілюструє роботу
програми для випадку N=22, D=2, H=8
