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