e-olymp 8663. Задача про множення

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані Вихідні дані
57 36
1000 729
7999 5103
28994 10368
4876 2268

 

Код програми

Алгоритм

Складність задачі полягає в обмеженості у часі.

  1. Знайдемо добуток цифр заданого числа.
  2.  Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
  3. Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

 

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

 

3 thoughts on “e-olymp 8663. Задача про множення

  1. Код будет легче читаться, если произведение цифр целого числа будет вычислять отдельная функция.
    Вы ищите максимум среди значений, которые последовательно вычисляете на основе исходного числа n. Зачем Вам для поиска максимума хранить все эти значения?! Просто сравнивайте очередное произведение с максимумом и двигайтесь дальше. Без массивов.
    Постарайтесь сделать код лаконичнее, 39 строк это многовато для такой задачи.
    И, пожалуйста, на этот раз полностью самостоятельно. уж Вам-то для этой задачи помощь точно не нужна.

  2. Хорошо.
    Но на мой взгляд объяснить и запрограммировать можно лаконичнее:

    Максимум произведения достигается либо на исходном числе, либо на числе меньшем на 1. Либо заканчивающемся на одну и более 9-ток. При этом та часть к которой дописываете девятки тоже уменьшается на 1.
    Нет, кажется простого объяснения у меня тоже не получилось 🙂

Добавить комментарий