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

 

e-olymp 1078. Степень строки

Постановка задачи

Обозначим через [latex]a\cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a=[/latex] «abc» и [latex]b=[/latex] «def», то [latex]a\cdot b=[/latex] «abcdef».
Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

[latex]a^{0}=[/latex] «» (пустая строка)
[latex]a^{n+1}=a\cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Входные данные:

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

Выходные данные:

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s=a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные Выходные данные
1 abcabcabc 3
2 aaaaaaaaaa 10
3 ollollo 1
4 pjpjpjpj 4

Посмотреть работу программы на примере приведенных выше тестов можно на сайте ideone.

Решение

Описание решения

Получая строку str из потока ввода, вызываем функцию static public int StringPow(final String str) и передаем полученную строку в качестве входного параметра. Функция StringPow возвращает значение типа int — наибольшую степень строки, которую программа и передаст в поток вывода в качестве выходных данных.

Минимальной степенью строки может быть число [latex]1[/latex] — в том случае, если в заданной строке [latex]s[/latex] нет повторяющихся подстрок. Максимальной же степенью строки может быть количество символов, из которых строка состоит — в том случае, если строка состоит из одного повторяющегося символа. В этом случае этот символ и будет считаться повторяющейся подстрокой.

Получив в качестве входного аргумента строку str, предположим внутри тела функции StringPow, что степень данной строки равна [latex]1[/latex] ( int pow = 1;) на тот случай, если бо́льшую степень найти не удастся.

Так как нужно найти число повторений подстроки минимального размера в строке str, будем проверять все подстроки размером от [latex]1[/latex] символа до size/2, где size — длина строки. Строка не может состоять из повторяющейся подстроки размером меньше [latex]1[/latex] или больше половины строки. Отсюда цикл for (int i=1; i<=size/2; i++).

Сразу будем отсеивать подстроки, из повторений которых строка не может состоять из-за несоответствия количества символов строки и подстроки ( if (size % i != 0) continue;). К примеру, строка длиной [latex]8[/latex] символов не может состоять из повторений подстроки длиной [latex]3[/latex] символа.

Запоминаем эту подстроку String sub1 = new String(str.substring(0, i));, а затем будем сравнивать с каждой следующей подстрокой такого же размера String sub2 = new String(str.substring(j, j+i)); во внутреннем цикле, предполагая перед этим, что мы нашли нужную нам подстроку ( boolean found = true;); если сверяемые подстроки различаются ( if (!sub1.equals(sub2))) — значит рассматриваемая подстрока sub1 искомой подстрокой не является. Прерываем действие внутреннего цикла и переходим к следующей подстроке, длиной на 1 символ больше. Если же строка полностью состоит из подстроки sub1 находим степень строки — число повторений подстроки в строке, иначе говоря, делим размер строки на размер подстроки ( pow = (size/i);).

Посмотреть решение задания можно на сайте e-olymp.