UniLecs #128_1. "Максимальное" разбиение числа
UniLecsЗадача: дано натуральное числа N. Необходимо разложить его на натуральные слагаемые таким образом, чтобы их произведение было максимальным.
Входные данные: N - натуральное число от 4 до 100
Вывод: максимальное произведение слагаемых при разбиении числа N
Пример:
N = 5
Answer = 6 (5 = 2 + 3 -> 2 * 3 = 6)
Реализация:
- @egormasharskii, C++: 2 метода решения: 1.5 балла
Например возмем 5. Если 5 разложить на сумму 3 и 2 , то видно что в таком случае произведение равно шести и вообще n <= 2^(n/2) и n <= 3^(n/3). Далее, функция 2*2*2...3*3 возрастает по мере увеличения числа троек. Из этого можно сделать вывод что нам выгоднее иметь как можно больше троек. Итак осталось только решить , что делать когда число не делится на 3. Остаток 2 - Тут все просто просто берем эту двойку. Остаток 1 - Уберем одну тройку и возьмем две двойки потому что 2*2>3*1
2. @TEXHIK, Java: 1 балл
Подробный разбор: https://docs.google.com/document/d/1_bU8y4AeAUjd4qCdJ6XoIHk2nCGP_ydFcvd9E5cs2II/edit
Test:
https://repl.it/@levon1550/T128
3. @jinxonik: 1 балл за первое решение + 2 * 0.5 балла за два доп.подхода + 15 * 0.1 балла за 15 доп.реализаций на различных языках = 3.5 балла!
Евгений сделал решение на 16-ти языках(!!!) программирования:
Ассемблеры:
• fasm 1 for Windows x64
• GNU Assembler (GAS) for Linux x64
• MASM/TASM for MS-DOS (.COM) [277 bytes with data]
Скриптовые:
• Python 3
• PHP
• JavaScript (для браузера) (Play-Test)
• Perl
• GolfScript (Play-Test)
• VBA for Excel
• CMD for Windows
Компилируемые:
• C
• C++ (Play-Test)
• Delphi
• Java
• C#
• Visual Basic.NET
МЕТОД 1
Переберём все числа от 2 до N-2 (т.к. 0 и 1 как множители нас не интересуют), обозначив их как i, вычтем из N и выполним рекурсию для получившейся разницы. Результат умножим на i. В качестве ответа используем максимальное произведение. Для N <= 4 возвратим N. Для ускорения результаты будем кэшировать. Псевдокод: return max(F(i)*F(N-i)) for i = 2..N-2
МЕТОД 2
Предыдущий метод можно оптимизировать, заменив рекурсию последовательным вычитанием из исходного значения числа 3-ки с перемножением этих троек, пока результат вычитания не станет меньше 5 (именно 5-ти, а не 4-х, т.к. иначе вычитая 3 из 4-х мы получим в качестве последних слагаемых 3 и 1, произведение которых меньше слагаемых 2 и 2). Результат умножаем на остаток (2, 3 или 4). Почему приоритет отдаётся именно тройкам, а не двойкам? Произведение троек всегда больше произведения двоек при том кол-ве каждой из этих цифр, при котором их суммы будут равны (например: 6 = 3+3 = 2+2+2; 3*3=9 > 2*2*2=8).
МЕТОД 3
Вычитать последовательно тройки из исходного числа - не самый лучший вариант. Поступим умнее: разделим исходное число на 3 и найдём остаток. Частное будет означать кол-во троек, которые нужно перемножить, а остатком будет последний множитель (оно же слагаемое, на которые мы разбиваем число N). Предусмотрим ситуацию, когда остаток равен 0 или 1. Ноль и единица как множители нас не интересуют - это мы выяснили ещё в методе №1, поэтому в этих случаях уменьшим частное на 1 (т.е. уменьшим число перемножаемых троек), а к остатку добавим 3. Итого получим ответ = 3^частное * остаток (с учётом коррекции).
Все реализации по ссылке ниже !
https://gist.github.com/jin-x/06be99774b17fb1b28715df362973957
Test Python:
https://repl.it/@jin_x/UniLecs-128-decomposepy
4. @ak0noplev, Python: 1 балл
Function splits input number by components which composition is max. The maximum composition can be achieved if we present the number as the set of 3's and 2's. Optimal way - calculate the maximum count of 3's in input number and present the remainder as 2's
https://gist.github.com/rtkn07/f798840f56ad16b19333a18c4d3f5361
Test:
https://repl.it/repls/AutomaticSupportiveAngles
5. Антон, Rust, Haskell: 1.1 балла
Подробный разбор смотри по ссылке ниже!
https://gist.github.com/AnthonyMikh/37009b5ad567e73a71f9899dbf511029
Test Haskell:
https://paiza.io/projects/TX_q88jWDmZH91Dt1G-ISQ?language=haskell
Test Rust:
https://play.rust-lang.org/?gist=e0da83d958af03e2ee39f4b57f4ede21
6. @lPestl, С++, F#: 1.5 балла за два метода решения + 0.1 балла за решение на доп.ЯП = 1.6 балла.
Пытаясь разложить небольшие числа на слагаемые, произведение которых максимально, то легко можно заметить закономерность, что максимальное произвидение достигается, когда большинство слагаемых = 3. Как это объснить, я пока не знаю, но с радостью воспользуюсь этой закономерностью. Используя это - выделим три частных случая:
1) когда число кратно трем, тогда можно его представить всеми тройками; N%3==0 => N=3+..(N/3 раз)..+3 => MaxP=3*..(N/3 раз)..*3
2) когда остаток от деления = 1, то 1 в произвидении не даст нам ничего, поэтому эту единицу лучше сложить с последней тройкой; N%3==1 => N=3+..(N/3 раз)..+3+1 = 3+..(N/3-1 раз)..+3+4 => MaxP=3*..(N/3-1 раз)..*3*4
3) когда остаток от деления = 2, то он и остаётся последним слагаемым и множителем N%3==2 => N=3+..(N/3 раз)..+3+2 => MaxP=3*..(N/3 раз)..*3*2
C++
https://gist.github.com/lpestl/4777f06d05d3b170f155e5dd8bac9b89
F#
https://gist.github.com/lpestl/096c212ed9131a59a20b1b1b6dc196a2
7. @nekoguy, Java: 1 балл
Разбор по ссылке ниже:
https://gist.github.com/NekoGuy/512529057a1ae855ab5c85cd8721bcad
8. @LostInKadath, Python: 1 балл
Из условия максимизации следует, что нам надо использовать как можно больше троек в разложении. В идеале n = 3x, а ответ к задаче — 3^x. Но что делать, если число не делится на три нацело? Здесь есть два случая:
1) n = 3x + 1: В этом случае мы теряем один множитель в итоговом разложении — умножение на единицу не меняет ответа. Но мы можем представить исходное число в ином виде и увеличить ответ: n = 3*(x-1) + 4, answer = 3^(x-1) * 4;
2) n = 3x + 2: В этом случае оставшаяся двойка будет играть роль последнего множителя, и мы получим: answer = 3^x * 2.
https://gist.github.com/LostInKadath/359939535ae19a68b4273e5c9b9d22f0
9. @voodoo_woodpecker, Python: 1 балл
Подход к решению
1. Разлагать надо на наименьшие возможные слагаемые 2 и 3, так как их произведение будет больше суммы для N>4, то есть, например, для пяти (2+3)<(2*3)
2. Разлагать надо на тройки, так как 3^x > 2^y, где x и y число троек и двоек при разложении числа N -- проверено для N=6, 12, 18, ..., 66; доказывать лень :)
3. Если в остатке остаётся 1, то выгоднее заменить .. + 3 + 1 на + 2 + 2, так как 3*1 < 2*2
https://gist.github.com/MikePeleah/c519bfd5381a4cd8ea0cefc0e0697404
Test:
https://repl.it/@MikePeleah/UniLecs128
10. @kirillmotrichkin, Python: 1.5 балла
Первый вариант
В первом решении - завуалированная рекурсия. Лучшее произведения разбиения числа X это либо разбиение числа X - 2, умноженное на 2, либо разбиение числа X - 3, умноженного на 3, либо X - 4, умноженного на 4.
Второй вариант
Можно заметить, что на 3 мы умножаем чаще всего. Видимо это связано в наибольшей экономичностью троичной системы счисления. Если число делится на 3, разбиваем на тройки. Если при делении на 3 в остатке 1 - нужно в разбиение включить 4, остальное - тройки. Если при делении на 3 в остатке 2 - нужно в разбиение включить 2, остальное - тройки
https://gist.github.com/superkiria/eb1ba54e63b3e4b6adbedef3fa5b622f
Test:
https://repl.it/@superkiria/unilecs128breakdown
11. @dbond762, GO: 1 балл
Разбиваем число на троойки.// Если в остатке 1 - вместо 3 + 1 пишем 2 + 2.
https://gist.github.com/dbond762/79383b9f43c8a130616eeedb39f8b3fc
Test:
https://play.golang.org/p/oB1S6ocvc9j
12. @rustem_b, Julia: 1 балл
Если число делится на три (число можно представить как сумму m троек), то произведение его слагаемых будет максимальным. Если при делении на 3 получаем остаток 1, то это значит, что нужно добавить ещё 1 к слагаемым n-1 (см условие выше), чтобы сумма m-1 троек и 4 (так как при умножении на 1 ничего не изменится) была этому же числу, следовательно и произведение будет максимальным. Если остаток равен 2, то нужно всего лишь добавить 2 к слогаемым n-2 (первое условие), так как 5k < 2×3k, значит и произведение будет максимальным.
https://gist.github.com/RustemB/168c919754fab04b3eebe987f050c6b2
13. @Zernov_A, Java: 1 балл
Число нужно разбивать на слагаемые: 2, или 3. Слагаемое "1" - сразу отбрасываем, т.к. оно никак нее влияет на произведение. Любые другие числа >3, можно разложить на более мелкие, которые дадут большее произведение: a+b <= a*b, a>=2, b>=2. Рассмотрим число 6: 6 = 2 + 2 + 2, 2*2*2 = 8; 6 = 3 + 3, 3*3 = 9. Таким образом, лучше разбивать число на максимальное кол-во 3-ек, и минимум 2-ек
https://github.com/AlexZDeveloper/SplittingNumber
Test:
https://repl.it/@AlexZDeveloper/SplittingNumber
14. @tvolf, PHP: 1 балл
Рассмотрим ситуацию, когда у нас число разбито на некоторые слагаемые. Все отдельные единицы мы можем добавить к любому слагаемому и от этого произведение только увеличится (1 * N = N). Затем, все слагаемые K, которые больше четырех, мы можем разбить на 3 * (K - 3). При этом итоговое произведение увеличится (5 < 3 * 2, 6 < 3 * 3, 7 < 3 * 4 и тд). Каждые три группы двоек мы можем заменить на 2 тройки, так как 2 * 2 * 2 < 3 * 3. Таким образом, нам нужно разбить исходное число на максимальное количесто троек, а в остатке у нас не должно быть единицы. Если остается единица, мы должно взять одну из троек и суммарное 4 либо оставить так, как есть, либо заменить на 2 двойки (2 * 2 = 4). Таким образом, в результате разделения на слагаемые у нас должны остаться в последовательности все тройки и 0, 1 либо 2 двойки.
https://gist.github.com/tvolf/5f2b4d4347135d1f1ad0251cbe1b1086
15. @akolosov364, JS: 1 балл
Число 4 можно разбить как 2 * 2, что не имеет смысла, т.к. не больше чем само число. Число 5 как 2 * 3, что больше чем 5 и уже имеет смысл. Число 6 как 3 * 3 или 2 * 2 * 2. Разбивать по тройкам оптимально. В разбиении n нельзя использовать 5, т.к. его уже можно разбить на 6. Соотвественно задача сводится к нахождению степени тройки на которую мы можем разбить число.
https://gist.github.com/KolosovAO/f2690907d8034069afef7dbf89762206
Test:
https://repl.it/@AlieksieiKoloso/task128
16. @as_yakovlev, Python: 0.5 балла
https://gist.github.com/YakovlevAl/085470dda5c91ea28d0dc4f49e26862a