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

Код програми

#include <iostream>
using namespace std;

int multiplication(int x) {
    int mul = 1;
    while(x != 0) {
        mul *= x % 10;
        x /= 10;
    }
    return mul;
}
int main() {
  int n;
  cin >> n;
  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;
    }  
    cout << maxmul; 
}

#include <iostream>

using namespace std;

int multiplication(int x) {

int mul = 1;

while(x != 0) {

mul *= x % 10;

x /= 10;

}

return mul;

}

int main() {

int n;

cin >> n;

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;

}

cout << maxmul;

}

Алгоритм

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

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

Приклад:

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

Посилання

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

Related Images:

Похожее

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

Мазурок Игорь Евгеньевич says: 11/01/2020 at 19:40

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

Войдите, чтобы ответить
- Эвелина Алексютенко says: 12/01/2020 at 14:02
  
  Благодарю Вас, я переделаю.

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

#include <iostream>
#include <cmath>
int f (int n) {
    int d = n % 10;
    while (n > 10) d *= (n /= 10) % 10;
    return d;
}
int main () {
    int N; std::cin >> N;
    int max = f(N);
    for(int d = 1; N > 0; N /= 10, d *= 9)
        max = std::max(max, d * std::max(1, f(N-1)));
    std::cout << max;
}

#include <cmath>

int f (int n) {

int d = n % 10;

while (n > 10) d *= (n /= 10) % 10;

return d;

int N; std::cin >> N;

int max = f(N);

for(int d = 1; N > 0; N /= 10, d *= 9)

max = std::max(max, d * std::max(1, f(N-1)));

std::cout << max;

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