Pakiranje piva

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Nino Bašić
  • UPM 2017

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Če kupim celo gajbo, v sobo se zaprem
in z vsemi pravo orgijo začnem.
Naslednja vsaka mi od prejšnje bolj diši.
Ko spijem vse, se od ljubezni mi vrti.
— Adi Smolar, Ljubim jo

Ivo je velik ljubitelj piva. Doma ima N različnih vrst piva v velikih količinah. Pivo ima v steklenicah, ki so vse enake velikosti. Število a_i prestavlja število steklenic piva i-te vrste. Ker je povabljen na zabavo, je sklenil, da bo vse svoje pivo peljal s seboj. Pri lokalnem embalažnem podjetju bo naročil kartonske škatle velikosti k, v katere bo spravil steklenice.

V škatlo velikosti k lahko zapakira k ali pa k - 1 steklenic. (Če v škatli manjka ena steklenica, je lahko brez bojazni, da bi se pri transportu kaj razbilo.) Poleg tega bo v vsako škatlo spravil samo steklenice enake vrste piva. Ker bi rad naročil čim manj škatel, ga zanima, kakšno je največje število k, da bo lahko zapakiral celotno zalogo piva.

Naloga

Napišite program, ki prebere podatke o Ivovi zalogi piva in izpiše največje število k, za katero velja, da bo Ivo lahko vse svoje pivo varno zapakiral v škatle velikosti k.

Vhodni podatki

V prvi vrstici se nahaja naravno število N, tj. število različnih vrst piva. Sledi N vrstic, pri čemer i-ta vrstica vsebuje naravno število a_i, tj. število steklenic piva i-te vrste.

Omejitve vhodnih podatkov

  • 1 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9

Izhodni podatki

Izpišite število k.

Primer

Vhod

4
9
20
8
13

Izhod

5
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task