#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <set>
// #include <unordered_map>
const int INF = 1000001;
std::vector<int> getMinMaxCuts(
int tShoLen, int tDif, int stickLen, int stickAmount);
bool tryMinDiffer(
int cuts, int tShoLen, int tDif,
std::unordered_map<int, int> &lenAmount,
std::set<int> stickLenSet);
void solveDotSolve(
int maxCuts,
std::unordered_map<int, int> &lenAmount,
std::set<int> &stickLenSet);
std::unordered_map<int, int> getInput(int &maxCuts,
std::set<int> &stickLenSet)
{
/*
changes maxCuts to the amount of cuts (m)
inserts different stick lens to set stickLenSet, it will have all lens in sorted order
returns lenAmount containing (len : amount) pairs
*/
int sticksAmount, stickLen;
std::unordered_map<int, int> lenAmount;
std::cin >> sticksAmount >> maxCuts;
for (int i=0; i<sticksAmount; i++) {
std::cin >> stickLen;
lenAmount[stickLen]++;
stickLenSet.insert(stickLen);
}
return lenAmount;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int maxCuts;
std::unordered_map<int, int> lenAmount;
std::set<int> stickLenSet;
lenAmount = getInput(maxCuts, stickLenSet);
solveDotSolve(maxCuts, lenAmount, stickLenSet);
return 0;
}
std::vector<int> getMinMaxCuts(
int tShoLen, int toler, int stickLen, int stickAmount)
{
/*
simple, get min and max cuts that can result in the stick ending up in rhe range
...turns out this ain't so simple...
*/
//
int minToler=tShoLen,
maxToler=tShoLen + toler,
minCutsAmount=0,
maxCutsAmount, remMinLen, remMaxLen;
// find most cuts
int piecesAmountMax = stickLen/minToler;
remMinLen = stickLen % minToler;
if (remMinLen / piecesAmountMax + bool(remMinLen % piecesAmountMax) > toler) return {INF, INF};
maxCutsAmount = stickLen / minToler - 1;
for (int bigToler=maxToler; bigToler>=minToler; bigToler--) {
// std::cout << " " << bigToler << " last\n"; // VERY GOOD
// jos tikku on liian pieni
if (stickLen < bigToler) continue;
piecesAmountMax = stickLen/bigToler;
// paljonko jää jäljelle kun jaetaan mahollisimman isoihin osiin
remMinLen = stickLen % bigToler;
// ??? muista käyttää
// jos jäljelle ei jää mitään, jako menee tasan
if (remMinLen == 0) {
minCutsAmount = piecesAmountMax - 1;
break;
}
// jos jäljelle jää liian pieni pätkä, katson jos sen voi jakaa muille osille ylittämättä rajaa
if (bigToler + remMinLen/piecesAmountMax + bool(remMinLen%piecesAmountMax) <= maxToler) {
minCutsAmount = piecesAmountMax - 1;
break;
}
remMaxLen = remMinLen + piecesAmountMax*(bigToler - minToler);
// jos jäljelle jää hyväksyttävän pitune pätkä
if (remMaxLen >= minToler) {
minCutsAmount = piecesAmountMax;
break;
}
}
// std::cout << " gMMC returns: " << minCutsAmount << " " << maxCutsAmount << " at " << tShoLen << " + " << toler << " " << stickLen << "\n"; // THE GOODEST
return {minCutsAmount, maxCutsAmount};
}
bool tryMinDiffer(
int cuts, int tShoLen, int tDif,
std::unordered_map<int, int> &lenAmount,
std::set<int> stickLenSet)
{
/*
cuts = how many cuts I must do
tShoLen = what the shortest stick should end up being
tDif = the largest difference between longest and shortest stick
lenAmount = contains (length : amount) pairs of sticks
***
maxUsedCuts = maximium amount of cuts to achive the range
minUsedCuts = minimium amount of cuts to achive the range
***
return = check if can be cut to get in range
*/
//
int maxUsedCuts=0, minUsedCuts=0, longstLen, longstAmount,
maxLoops = static_cast<int>(stickLenSet.size());
std::vector<int> minMaxCuts;
// find least and most amounts of cuts to get all sticks in the acceptable range
// if cuts not in this range, return bigger than acceptable num
for (int i=0; i<maxLoops; i++) {
// cut longest stick into the range each loop
longstLen = static_cast<int>(*stickLenSet.rbegin());
if (longstLen < 2*tShoLen) break;
longstAmount = lenAmount[longstLen];
stickLenSet.erase(--stickLenSet.end());
// std::cout << " params gMMC: " << tShoLen << " " << tDif << " "
// << longstLen << " " << longstAmount << "\n";
minMaxCuts = getMinMaxCuts(tShoLen, tDif, longstLen, longstAmount);
minUsedCuts += longstAmount*minMaxCuts[0];
maxUsedCuts += longstAmount*minMaxCuts[1];
// std::cout << " " << minUsedCuts << " " << cuts << " " << maxUsedCuts << "\n";
if (minUsedCuts > cuts) return false;
}
if (stickLenSet.size() != 0)
if (*(--stickLenSet.end())>tShoLen+tDif)
return false;
if (minUsedCuts <= cuts and maxUsedCuts >= cuts) return true;
return false;
}
void solveDotSolve(
int maxCuts,
std::unordered_map<int, int> &lenAmount,
std::set<int> &stickLenSet)
{
int longst = static_cast<int>(*(--stickLenSet.end())),
shorts = static_cast<int>(*(stickLenSet.begin())),
startDif=0;
int maxDiffer = longst - shorts,
minDiffer = maxDiffer;
// int thisLoopCount = 0;
bool valid = false;
// std::cout << "\n";
// for (auto i : stickLenSet) std::cout << i << " ";
// std::cout << "\n\n";
int cuts = 1, shortsTemp, longstTemp, secLongst = *(----stickLenSet.end());
if (longst > 2*shorts)
shortsTemp = shorts;
else
shortsTemp = longst/2;
if (longst > secLongst*2)
longstTemp = longst/2 + longst%2;
else
longstTemp = secLongst;
for (; cuts<lenAmount[longst]+1; cuts++) { //händlää pisimmät
if (cuts < lenAmount[longst])
std::cout << longst - shortsTemp;
else
std::cout << longstTemp - shortsTemp << " ";
}
// std::cout << "\n" << shortsTemp << "\n";
int piecesAmountMax, remMinLen, neccCuts=0;
bool breakThis = false;
for (; cuts<maxCuts+1; cuts++) {
minDiffer = maxDiffer;
// do with every cut amount k = 1, 2, 3, ..., m
for (int tDif=startDif; tDif < longst; tDif++) {
// have a target len for the shortest possible stick in the end, tShoLen
for (int tShoLen=shortsTemp; tShoLen > 0; tShoLen--) {
breakThis = false;
// figure out if you can reach the range at all
for (auto stickLen : stickLenSet) {
piecesAmountMax = stickLen/tShoLen,
remMinLen = stickLen % tShoLen;
if (remMinLen / piecesAmountMax + bool(remMinLen % piecesAmountMax) > tDif) {
neccCuts++;
// thisLoopCount++;
breakThis = true;
break;
}
}
if (breakThis) continue;
// std::cout << tDif << " " << tShoLen << "\n";
// have a maximium difference of the shortest (tShoLen) and longest stick in the end
// attempt to get all sticks in range [tShoLen, tShoLen+tDif]
// std::cout << "params: " << cuts << " " << tShoLen << " " << tDif << "\n";
valid = tryMinDiffer(cuts, tShoLen, tDif, lenAmount, stickLenSet);
if (valid) {
minDiffer = tDif;
// std::cout << "valid\n";
break;
}
}
if (valid) {
break;
}
}
// std::cout << " " << minDiffer << "\n";
std::cout << minDiffer << " ";
}
// std::cout << "\n" << thisLoopCount << "\n";
}
