Deljenje

View as PDF

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

Dato je N čokolada. Čokolada sa indeksom i ima A_i kockica. Nastavnica želi da čokoladu podeli deci, tako da svako dete dobije celu čokoladu, ili bar deo jedne. Nastavnica može uzeti jednu čokoladu, i podeliti je na 2 jednaka dela(Ako je inicijalan broj kockica u čokoladi bio neparan, jedan deo će imati jednu kockicu više). Nastavnica ne može podeliti deo koji je veličine jedne kockice. Na kraju, svako dete mora dobiti celu čokoladu, ili deo jedne čokolade(Ne može dobijati kockice iz različitih čokolada). Nastavnici može da ostane višak čokolada. Nastavnica želi da najmanja količina čokolade koju neko dete dobije bude najveća moguća.

Opis ulaza

U prvoj liniji standardnog ulaza unose se brojevi N i K (1 \le N,K \le 10^5), koji označavaju broj čokolada i broj dece. U drugoj liniji standardnog ulaza unose se elementi niza A (1 \le A_i \le 10^9), razdvojeni sa po jednim razmakom, koji označavaju veličinu čokolada.

Opis izlaza

U prvoj liniji standardnog izlaza ispisati maksimalan broj kockica koje može dobiti dete sa najmanjom količinom čokolade.

Primer
Standardni ulaz          Standardni izlaz
4 6
50 20 25 10
12
Objasnjenje test primera

Podelili smo cokoladu velicine 50 na 2 od po 25, pa smo te cokolade od 25 podelili na 12 i 13. Sada imamo velicine 20 25 10 12 12 13 13. Bilo kakvim daljim deljenjem ne moze se poboljsati rezultat. Rezultat je 12.

Ograničenja i podzadaci

(1 \le N, K \le 10^5)
( 1 \le A_i \le 10^{9} )

Test primeri su podeljeni u 3 disjunktne grupe:
U test primerima vrednim 30 poena: (1 \le N, K \le 1000).
U test primerima vrednim 30 poena: (1 \le A_i \le 10^5).
U test primerima vrednim 40 poena: Nema dodatnih ograničenja.


Comments

There are no comments at the moment.