Papirici

View as PDF

Submit solution

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

Author:
Problem type

Perica je oduvek voleo igre na sreću, pa je smislio jednu za svog druga Jovicu. Perica uzme n papirića, na svakom papiriću napiše po jedan broj i okrene ih tako da Jovica ne zna koji su brojevi napisani. Zatim Jovica mora da rasporedi sve papiriće na proizvoljan broj gomila. Svaka gomila mora da ima najmanje 2, a najviše k papirića. Na kraju Perica otkrije sve papiriće, te računa broj poena koji je Jovica osvojio.

Perica računa poene na sledeći način: Pronađe najveći i najmanji broj na jednoj gomili i izračuna njihovu razliku. Kada izračuna razliku najvećeg i najmanjeg za svaku gomilu, sabere sve razlike. Dobijena vrednost predstavlja osvojene poene. Što je broj poena manji, to je Jovica uspešniji.

Znajući koje brojeve je Perica napisao na papiriće, odredite koliko najmanje poena Jovica može da sakupi.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulaza nalaze se dva broja n i k (2 ≤ kn ≤ 100.000) koji predstavljaju, redom, broj papirića i maksimalnu veličinu gomila. U drugom redu se nalazi n celih brojeva, koji predstavljaju brojeve napisane na papirićima. Svi brojevi će biti u intervalu [-231, 231 - 1].

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlaza ispisati najmanji broj poena koji može da se sakupi. Rešenje će uvek postojati.

Primer:

standardni ulaz      standardni izlaz
7 3
6 0 5 2 8 0 -2
        
7

Objašnjenje.

Na prvu gomilu se stave papirići sa brojevima 0 i 2, na drugu gomilu papirići sa 6, 5 i 8, a na treću papirići sa 0 i -2. Ukupan broj poena je (2 - 0) + (8 - 5) + (0 - (-2)) = 7

Napomena.

U 30% test primera biće k ≤ 100.


Comments

There are no comments at the moment.