Задача
На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [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 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.Scanner; public class Main { static int multiplication(int x) { int mul = 1; while(x != 0) { mul *= x % 10; x /= 10; } return mul; } public static void main (String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int maxmul = multiplication(n); int copy = n; int i = 10; while(n!= 0) { int temporary_number = (copy / (i / 10)) % 10; int left = copy / i; int right = copy % (i / 10); if(temporary_number != 9) { temporary_number = 9; copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right; } n /= 10; i *= 10; int mul = multiplication(copy); if(maxmul < mul) maxmul = mul; } System.out.println(maxmul); } } |
Алгоритм
Складність задачі полягає в обмеженості у часі.
- Знайдемо добуток цифр заданого числа.
- Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
- Порівнюємо поточний добуток з максимальним.
Приклад:
Приклад розкладу числа на різних етапах алгоритму:
Посилання
Задача на e-olymp
Зарахований розв’язок
Код на ideone