Пуно фигурица
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 0,2 s | 64 Mb | standardni izlaz | standardni ulaz |
Овај задатак је поновљен у циљу увежбавања различитих техника решавања.
Друштвену игру игра \(k\) играча и сваки играч игру почиње са по \(k\) фигура, при чему све фигуре једног играча морају бити исте јачине, док су јачине фигура различитих играча различите. Фигуре су доступне у неограниченим количинама, при чему је познат низ јачина доступних фигура. Напиши програм који одређује највећи број играча \(k\) који могу играти игру тако да разлика између укупне јачине свих фигура било која два играча не пређе задату границу.
Улаз
Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 10^5)\), а затим у наредном реду \(n\) различитих расположивих јачина фигура (природни бројеви између \(1\) и \(10^5\)). Наредни ред садржи границу (природни број између \(1\) и \(10^{12}\)).
Излаз
На стандардни излаз исписати два броја раздвојена размаком – број \(k\) и најмању разлику укупних јачина фигура када игра \(k\) играча.
Пример
Улаз
5 5 4 2 7 3 15
Излаз
4 12
Објашњење
Ако играчи узму по четири фигуре јачине \(5\), \(4\), \(2\) и \(3\) највећа разлика јачина фигура играча биће \(4\cdot 5 - 4\cdot 2 = 12\). Ако би играло \(5\) играча, морали би да узму и фигуре јачине \(7\) и највећа разлика би била \(5\cdot 7 - 5\cdot 2 = 25\), што је веће од дозвољене границе.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.