UniLecs #137_1. Multiplication of digits

UniLecs #137_1. Multiplication of digits

UniLecs

Задача: дано натуральное число N. Необходимо найти наименьшее натуральное число, в ктр произведение его цифр было бы равно N. Если такого числа не существует, вывести -1.

Входные данные: N - натуральное число от 1 до 10^9.

Вывод: наименьшее натуральное число, произведение цифр ктр было бы равно N. -1 - если такого числа нет.

Пример:

N = 11; Answer = -1

N = 12; Answer = 26

N = 14; Answer = 27

Season Cup 5:

Турнирная таблица

Реализация:

  1. Andrew Bystrov, Java: 1 балл
Идея заключается в том, что необходимо разложить данное число N так, чтобы все его сомножители были меньше 9 (т.е. произвести факторизацию числа так, чтобы все сомножители были <= 9) ( ну и очевидно, больше 2) Иначе может получится ситуация, если сомножитель будет больше чем 9 (т.е. число вида ab) и тогда, мы можем предположить, что результат у нас должен быть в виде q*w*e*...*ab. Но это не сработает, т.к. мы должы по условию делать q*w*e*...*a*b. Логично, что для простых чисел мы всегда вернем -1. Соответственно, если мы в какой то момент времени видим, что числе не делится на число из диапазона 2-9, значит выводим -1. Иначе запоминаем все цифры и выводим их в порядке возрастания. Начнем делить мы с 9 до 2, т.к. у нас может возникнуть ситуация ( если мы будем делить с 2 по 9), например, с числом 100 что мы поделим 100 /2 = 50, и потом 50/2 = 25. Значит у нас будет уже цифры 2 и 2, хотя если бы мы делили в обратном порядке, то мы сразу бы дошли до 5 ( 100 / 5 = 20), потом снова до 5 ( 20 / 5 = 4) и уже полчили 4 => ответ 455

https://gist.github.com/AndrewBystrov/bcf5089e9a2bdc4b70ecb6d7e109eb5d


2. @akolosov364, JS, Rust: 1.1 балла

Задача сводится к поиску всех делителей числа. Если число имеет простой делитель больше 10, то задача не имеет решения. Имеет смысл искать делители, начиная с 9. Это сократит количество чисел в записи числа: 9=3х3, 8=2х4, 6=2x3, 4=2x2. Как только все делители были найдены, достаточно их просто перевернуть чтобы получить ответ.
@akolosov364, JS

https://gist.github.com/KolosovAO/057af7e0d6e082595c4547deadf47965

Test:

https://repl.it/@AlieksieiKoloso/task137

Rust:

https://gist.github.com/KolosovAO/66302ad6e15d76f0d2090b2f64443867

Rust Test:

https://repl.it/@AlieksieiKoloso/task137rust


3. @jinxonik, 24 ЯП (1 + 0.5 балла за доп.метод с помощью разложения числа на простые множители + 0.1 балл за доп.модификацию на Python + 25 *0.1 доп.реализации на различных ЯП) = 4.1 балла

Метод 1: Через последовательное деление на разные цифры
Метод 2: Разложение числа n на простые множители. Возвращает словарь формата {множитель: степень}
@jinxonik, С

https://gist.github.com/jin-x/4af215a71f8c6693812e71da1d6b54a5

Компилируемые:

1. C : Test

2. C++ [изменённый метод в сравнении с C]

2а. C++ [шаблон + constexpr: расчёт на этапе компиляции, программа только выводит результаты]

3. C#

4. Java

5. Delphi 7

6. PascalABC.NET

7. Rust

8. Go

9. Visual Basic .NET


Ассемблеры:

10. fasm 1 for Windows x64

10а. fasm 1 for Windows x86 (32-bit) [расчёты через макросы во время компиляции, программа только выводит результаты]

11. MASM32 for Windows x86 (32-bit) [алгоритм, возвращающий строку, а не число]

12. GNU Assembler (GAS, AT&T syntax) for Linux x64

13. TASM for MS-DOS (.COM) [исполняемый код - 318 байт, включая 140 байт данных]


Скриптовые:

14. Python 3

15. PHP

16. JavaScript

17. Ruby

18. Perl

19. Lua

20. VBScript

21. VBA for Excel

22. CMD for Windows (+ модицикация)

23. Bash for Linux

24. GolfScript (+ модицикация) [эзотерический]


4. @TEXHIK, Java: 1 балл

Чем больше множителИ, тем меньше множителЕЙ. А чем меньше множителей тем меньше порядок. Так что факторизуем бьём начиная с самых больших цифр.

https://repl.it/@levon1550/T137


5. Антон, Rust: 1 балл

Подробный разбор смотрите в gist файле:

https://gist.github.com/AnthonyMikh/750c4d9bec3be66bcce28197494367de

Test:

https://play.rust-lang.org/?gist=5150d56ba5b6781dfe662bd61718a575


6. @kupp1, Python: 1 балл

Пусть n - введенное число. Пусть p - число, которое требуется составить. Подобную задачу можно свести к более строгому условию: необходимо найти такое сочетание цифр от 2 до 9, произведение которых даст какое-то определенное число n. Далее необходимо составить из найденных цифр минимально возможное число p. Я исключаю из этого диапазона 1 и 0, так как 1 результат произведения не изменит, а 0 - превратит его в 0. По основной теореме арифметики есть только один способ разложить число на простые делители. Этим и воспользуемся: найдем простые делители числа n факторизацией и будем пробовать составить число p из этих простых чисел. Логично, что перемножение простых делителей числа n даст нам само число n, остается только определить, что если хотя бы один из простых делителей не однозначен (т.е двухзначен, трехзначен и т.д.) то по такому числу n число p составить невозможно. Таким образом, мы можем работать только с однозначными простыми делителями, т.е. только с делителями 2, 3, 5, 7 - это единственные однозначные простые числа. У нас есть определение случая, когда задача не решаема. Когда задача решаема, у нас есть набор простых однозначных чисел, из который надо составить число p. Всего у нас может получится 8 цифр в числе p:
  • 9 - 3*3
  • 8 - 2^3
  • 7 - есть изначально
  • 6 - 2*3
  • 5 - есть изначально
  • 4 - 2^2
  • 3 - есть изначально
  • 2 - есть изначально
Наша задача сначала найти количество 9, потом 8, и т.д. от большего у меньшему. Изначально в цикле мы просто подсчитываем количество цифр 2,3,5,7. Далее, вычисляем количество 9: это количество пар троек (не забываем уменьшить кол-во троек) и так далее. Потом выводим в одну строчку все наши возможные цифры от меньшей к большей. Число p вычислено.

https://gist.github.com/kupp1/4e2f32320a2cbc68dcd9e52bebcbb46a


7. @egormasharskii, C++: (1 + 0.5 балла за Метод 3 + 0.3 балла за Метод 2 с оптимизацией 1го метода) = 1.8 балла

Метод 1: Brute force. Раскладываем число на все возможные множители от 2 до 9 и выбираем наименьшее число составленное из них.
Метод 2: Brute force optimization. Поскольку в разложении числа перестановка множителей ничего не меняет, мы можем использовать этот факт и в предыдущем решении использовать кэширование.
Метод 3: Можно заметить, что чем больший делитель мы выбираем, тем меньше становится оставшаяся часть и тем меньше разрядов будет в ответе. Поэтому можно избавиться от перебора и искать делители не от 2 до 9, а от 9 до 2. В таком случае мы получим минимальное по количеству разрядов число в ответе при первом же разложении. Единственное что там останется сделать - это поменять порядок цифр в ответе чтобы максимальные делители ушли в младшие разряды.

http://cpp.sh/9l6xa


8. @DaurenAbd, C++: 1 балл

Смотри разбор в gist файле:

https://gist.github.com/DaurenAbd/8f0ad2410ec5531df1d5336b6527f356


9. @LostInKadath, C++: 1 балл

По сути задача сводится к факторизации числа - нахождению его множителей. Но вводится дополнительное ограничение - множители не должны превышать 10, ибо они выражаются цифрами.Здесь реализован самый простой вариант факторизации - перебор. Перебор делителей осуществляется с бОльших цифр к меньшим.Полученные делители складываются в вектор и сортируются в возрастающем порядке для получения минимального числа.Если на каком-то шаге алгоритм не находит делитель в интервале [2, 9], происходит возвращение к предыдущему шагу и проба другого делителя.

https://gist.github.com/LostInKadath/a246e89e5cae17fa534166d59e68a096


10. @Rusik666, C++: 1 балл

Разбор решения смотри в gist-файле:

https://github.com/ruslan1979/unilecs/blob/master/task137.cpp


11. @voodoo_woodpecker, Python: (1 + 0.3 балла за доп.решение с помощью оптимизации первого алгоритма + 0.1 балла за доп.ЯП) = 1.4 балла

Метод 1. Сначала разбиваем число на простые множители-цифры (2,3,5,7)# Потом комбинируем множители в наиболее эффективные комбинации.
Метод 2. Чтобы не мучиться с заменой комбинаций множителей на втором этапе# просто ищем их в оптимальном порядке: 9(3x3) > 8 (2x2x2) > 6 (2x3) > 4 (2x2) > 3 > 2, остальное (5, 7) неважно, ибо не комбинируется.

https://gist.github.com/MikePeleah/8dbafe95acc7cd6f9b4663279531c9fc

Test:

https://repl.it/@MikePeleah/UniLecs137Py

JS:

https://gist.github.com/MikePeleah/a8c7e0ebca4251a2ce2ee049037142fb

Test JS:

https://repl.it/@MikePeleah/UniLecs137JS


12. @kirillmotrichkin, Python: 1.5 балла

Метод 1. Будем делить заданное число на числа меньше 10, то есть цифры. Если будет получаться деление, то записываем делитель в ответ и продолжаем ту же работу с частным.
Метод 2. Будем делить заданное число на числа меньше 10, то есть цифры. Если будет получаться деление, то записываем делитель в ответ и продолжаем ту же работу с частным. Рекурсия здесь выглядит красивее!

Метод 1:

https://gist.github.com/superkiria/1c4d1743272d2b0ff9053652f6334a38

Test:

https://repl.it/@superkiria/unilecs137-1multiplicationofdigits

Метод 2:

https://gist.github.com/superkiria/b2d3c08ff924323b68816df38e7ca445

Test:

https://repl.it/@superkiria/unilecs137-2multiplicationofdigits


13. @lPestl, C#: 1 балл

Смотри подробный разбор в gist-файле:

https://gist.github.com/lpestl/0b8912a2aa45d377ec10ab4a622854d4