#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Frac2
{
int number;
int divisor;
double result;
void update()
{
result = (double)number / (double)(divisor + 1);
}
Frac2(int _number, int _divisor)
{
number = _number;
divisor = _divisor;
update();
}
bool operator<(Frac2 frac) const
{
return result < frac.result;
}
};
multiset<Frac2> numbersSorted2;
void printSet2()
{
cout << "printing set:\n";
for (Frac2 frac : numbersSorted2) {
cout << frac.number << " " << frac.divisor << " " << frac.result << "\n";
}
}
void getWorkingDifference(vector<int>& results)
{
Frac2 fracSmall = *numbersSorted2.begin();
int smallestNumber = fracSmall.number / fracSmall.divisor;
Frac2 fracBig = *numbersSorted2.rbegin();
int biggestNumber = fracBig.number / fracBig.divisor;
if (fracBig.number % fracBig.divisor != 0) {
biggestNumber += 1;
}
results.push_back(biggestNumber - smallestNumber);
cout << results.back() << " ";
}
void runWorkingProgram(int n, int m, vector<int>& testNumbers, vector<int>& results)
{
cout << "STARTINGWORKINGPROGRAM\n";
for (int i = 0; i < n; i++) {
int number;
//cin >> number;
number = testNumbers[i];
numbersSorted2.emplace(number, 1);
}
for (int k = 0; k < m; k++) {
printSet2();
Frac2 frac = *numbersSorted2.rbegin();
Frac2 newFrac = Frac2(frac.number, frac.divisor + 1);
numbersSorted2.erase(--numbersSorted2.end());
//cout << "size = " << numbersSorted.size() << "\n";
numbersSorted2.insert(newFrac);
//cout << "size = " << numbersSorted.size() << "\n";
getWorkingDifference(results);
}
//printSet();
cout << "ENDINGWORKINGPROGRAM\n";
}
struct Frac
{
int number;
int divisor;
int resultBigger;
Frac(int _number, int _divisor)
{
number = _number;
divisor = _divisor;
resultBigger = _number / _divisor;
if (_number % _divisor != 0) {
resultBigger += 1;
}
}
bool operator<(Frac frac) const
{
if (resultBigger == frac.resultBigger) {
//cout << "first = " << (number / (divisor + 1)) << "\n";
//cout << "second = " << (frac.number / (frac.divisor + 1)) << "\n";
return (number / (divisor + 1)) < (frac.number / (frac.divisor + 1));
}
return resultBigger < frac.resultBigger;
}
};
multiset<Frac> numbersSorted;
int minNumber = INT_MAX;
void printSet()
{
cout << "printing set:\n";
for (Frac frac : numbersSorted) {
cout << frac.number << " " << frac.divisor << " " << frac.resultBigger << "\n";
}
}
int getWorkingDifference()
{
Frac fracBig = *numbersSorted.rbegin();
int biggestNumber = fracBig.number / fracBig.divisor;
if (fracBig.number % fracBig.divisor != 0) {
biggestNumber += 1;
}
return biggestNumber - minNumber;
}
void shuffle(int& n, int& m, vector<int>& testNumbers)
{
minNumber = INT_MAX;
n = (rand() % 1000) + 1;
int sum = 0;
numbersSorted2.clear();
numbersSorted.clear();
testNumbers.clear();
for (int i = 0; i < n; i++) {
int random = (rand() % 10) + 1;
testNumbers.push_back(random);
sum += random;
}
sum -= n;
m = min(min((rand() % 1000) + 1, sum), 2);
}
int main()
{
/*Frac frac1(14, 7);
Frac frac2(13, 9);
cout << (frac1 < frac2) << " " << (frac2 < frac1);
return 0;*/
/*cout << "start";
for (int x = 0; x < 100; x++) {
for (int y = 0; y < 100; y++) {
for (int xd = 1; xd < 100; xd++) {
for (int yd = 1; yd < 100; yd++) {
if (x == y) {
continue;
}
Frac fracX(x, xd);
Frac fracY(y, yd);
if ((fracX < fracY) == (fracY < fracX)) {
//cout << "yes = " << x << " " << y << " " << xd << " " << yd << "\n";
Frac fracX1(x, xd + 1);
Frac fracY1(y, yd + 1);
int minX = fracX.number / fracX.divisor;
int minY = fracY.number / fracY.divisor;
int minX1 = fracX1.number / fracX1.divisor;
int minY1 = fracY1.number / fracY1.divisor;
int maxX = minX;
if (fracX.number % fracX.divisor != 0) {
maxX += 1;
}
int maxY = minY;
if (fracY.number % fracY.divisor != 0) {
maxY += 1;
}
int maxX1 = minX1;
if (fracX1.number % fracX1.divisor != 0) {
maxX1 += 1;
}
int maxY1 = minY1;
if (fracY1.number % fracY1.divisor != 0) {
maxY1 += 1;
}
if (!(min(minX, minY1) == min(minY, minX1))) {
cout << "WHAT\n";
cout << x << " " << y << " " << xd << " " << yd << "\n";
cout << minX << " " << minY << " " << minX1 << " " << minY1 << "\n";
}
}
}
}
}
}
cout << "end";
return 0;*/
int n, m;
//cin >> n >> m;
//n = 3; m = 9; vector<int> testNumbers = {3, 4, 5};
//n = 2; m = 6; vector<int> testNumbers = {2, 6};
//m = 9; vector<int> testNumbers = {1000, 999, 999, 500, 500, 100}; n = testNumbers.size();
//m = 10; vector<int> testNumbers = {3, 5, 5, 9, 9}; n = testNumbers.size();
m = 10; vector<int> testNumbers = {10, 11}; n = testNumbers.size();
for (int test = 0; test < 1; test++) {
shuffle(n, m, testNumbers);
//vector<int> resultsWorking;
//runWorkingProgram(n, m, testNumbers, resultsWorking);
for (int i = 0; i < n; i++) {
int number;
//cin >> number;
number = testNumbers[i];
minNumber = min(minNumber, number);
numbersSorted.emplace(number, 1);
}
//cout << "min number = " << minNumber << "\n";
//if (test == 1)
//printSet();
for (int k = 0; k < m; k++) {
//cout << "k=" << k << "\n";
//if (test == 1)
//printSet();
Frac frac = *numbersSorted.rbegin();
Frac newFrac = Frac(frac.number, frac.divisor + 1);
numbersSorted.erase(--numbersSorted.end());
//cout << "size = " << numbersSorted.size() << "\n";
numbersSorted.insert(newFrac);
minNumber = min(minNumber, newFrac.number / newFrac.divisor);
//cout << "size = " << numbersSorted.size() << "\n";
int ans = getWorkingDifference();
cout << ans;
if (k != m - 1) {
cout << " ";
}
}
//cout << "end";
//if (test == 1)
//printSet();
}
}
