Авторський розв'язок задач Mult2020(NetOi2020 Iетап)

Умова

Задача Mult2020. Натуральне число n розбийте на k натуральних доданків так, щоб добуток цих доданків був максимальним.

Програма Mult2020 вводить з пристрою стандартного введення через пропуск числа n і k (1≤k≤n≤1000). Програма виводить на пристрій стандартного виведення за неспаданням k натуральних чисел – шукані доданки.

Приклад

Введення	Виведення
5 2	2 3

Розв'язування

Математична модель

Розглянемо спочатку найпростіший випадок. Коли будь-яке число N необхідно розбити на 2 доданки, так щоб їх добуток був найбільший. Насправді, можна легко довести, що добуток буде найбільший, якщо число розбити на два доданки, які дорівнюють половині числа. Або, якщо число непарне, то на доданок, який дорівнює половині числа, а друге число буде на один збільшене. Наприклад, якщо число 11=5+6, 5*6=30. Якшо 12=6+6, 6*6=36.

Дійсно, половина числа N рівна N/2. Тоді N=N/2+N/2. А добуток цих доданків буде рівний (N/2)*(N/2)=N²/4

Тепер давайте один доданок зменшимо на один, а другий збільшимо на один. Таким чином, ми отримаємо наступну пару доданків і перевіримо, чи в нас вийде більше число чи меньше. N=(N/2+1)+(N/2-1). (N/2+1)*(N/2-1)=N²/4-1. Ми бачимо, що N²/4-1<N²/4 рівно на 1. Тобто, добуток при цьому зменшився на 1. Тепер, перший доданок зменшимо на 2, а другий збільшимо на 2. N=(N/2-2)+(N/2+2). (N/2-2)*(N/2-2)=N²/4-4. Тобто, чим більше ми будемо зменшувати один доданок і збільшувати інший доданок, який рівний половині числа, тим менший ми добуток будемо отримувати. Давайте перевіримо це на реальному прикладі.

Нехай в нас є число 10. 10/2=5. 10=5+5. 5*5=25.

5-1=4,5+1=6. 6+4=10. 6*4=24.

5-2=3,5+2=7 7+3=10 7*3=21.

Тобто, на реальному прикладі це працює. Таким самим способом можна довести це і для непарних чисел. І для того випадку, коли число треба поділити на більшу кількість доданків чим 2. Завжди треба розділити число порівну на кількість доданків. Наприклад, якщо в нас є число 36, і його треба розбити на 6 доданків. То найбільший добуток буде тоді, коли всі доданки будуть рівні 48/6=8. 8*8*8*8*8*8=262144. Останнє, що необхідно з'ясувати, які будуть доданки, якщо число націло не ділиться на кількість доданків. Наприклад, 51 розбити на 8 доданків. Для того, щоб знати, які будуть доданки, необхідно націло поділити N/K. Тобто, 51/8=6. Знайти остачу від ділення на 8. В C++ це записується так: N%K. 51%8=3.Тоді, нам цю остачу необіхдно розподілити порівну між всіма доданками по 6. Тобто, на скільки це можливо позбільшувати доданки на 1. В нашому випадку остача 3, тому три доданки будуть числом N/K+1. В нашому випадку 6+1=7. А K-N%K нам дасть кількість доданків, які просто необхідно вивести як N/K=51/8=6. В нашому випадку 8-3=5. Тобто, необхідно вивести п'ять шістірок і три рази число 7. Тобто, 51=6+6+6+6+6+7+7+7

Реалізація

#include<iostream>
using namespace std;
int main(void){
int n,k,a,b,i,c,d; //створюєму змінні цілого типу, в даній задачі обмеження по введених даних (1≤k≤n≤1000). Тобто максимальне число вхідних даних 1000, а наші обрахунки тільки будуть зменшувати дані записані в комірках, тому типу int буде достатньо
cin>>n>>k;//Вводимо число, яке буде розбиватися на доданки і кількість доданків
a=k-n%k;//В змінній a зберігай кількість доданків, які необхідно вивести без збільшення на 1.
b=n%k;//В змінній b зберігаєм кількість доданків, які необхідно вивести із збільшенням на 1, якщо остача n%k=0, то в b буде записано 0.
c=n/k;//В змінній c зберігаємо чому дорівнює n розділене на кількість доданків.
d=с+1;//В зміннй d зберігаємо число c збільшене на 1.
for(i=0;i<a;i++)//Циклом for a-разів виводимо змінну c
cout<<c<<" ";
for(i=0;i<b;i++)//Циклом for b-разів виводимо змінну d, якщо b=0, то цей цикл не запуститься і пропуститься
cout<<d<<" ";
return 0;
}