|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Magacin
|
Dobili ste posao magacionera u novom magacinu kutija! Magacin je ogroman i u njemu se
nalazi n gomila kutija, u svakoj gomili su kutije poređane jedna na drugu. Međutim, neke
gomile su previsoke a neke preniske, a vi volite red, pa ste rešili da prerasporedite neke kutije.
Na raspolaganju vam je viljuškar koji odjednom može da prenosi tačno k kutija (ni manje
ni više). Prema tome, u jednom prebacivanju možete uzeti tačno k kutija sa neke gomile
(koja ima bar k kutija) i prebaciti ih na bilo koju drugu gomilu. Želite da izvršite
nekoliko prebacivanja tako da na kraju dobijete n što približnijih gomila, tj. da razlika
broja kutija na najvećoj i najmanjoj gomili bude minimalna. Odredite tu razliku.
Ulaz:
(Ulazni podaci se nalaze u datoteci magacin.in.)
U prvom redu ulazne datoteke nalaze se 2 prirodna broja n i k koji predstavljaju,
redom, broj gomila i kapacitet
viljuškara (1 ≤ n, k ≤ 106). Sledeći red sadrži n brojeva
ai razdvojenih razmakom - broj kutija na odgovarajućim gomilama
(1 ≤ ai ≤ 109).
Izlaz:
(Izlazne podatke upisati u datoteku magacin.out)
U prvom i jedinom redu
izlazne datoteke ispisati minimalnu moguću razliku između broja kutija na najvećoj i
najmanjoj gomili posle optimalnog niza prebacivanja.
Primer:
magacin.in
|
|
magacin.out
|
5 7
20 3 8 19 29
|
|
6
|
Objašnjenje.
Ukoliko prebacimo 7 kutija sa prve na drugu gomilu, 7 kutija sa pete na drugu
i 7 kutija sa pete na treću, dobijamo gomile 13 17 15 19 15 gde je razlika između najveće
i najmanje 19 - 13 = 6. Nijedan drugi niz prebacivanja ne daje manju razliku.
|
|
fajl: magacin.cpp
|
#include <cstdlib>
#include <cstdio>
#include <memory.h>
const int MaxN = 1000100;
const int MaxK = 1000010;
int n, k, a[MaxN], r[MaxN], sorted[MaxN], c[MaxK];
int main() {
FILE* inFile = fopen("magacin.in", "r");
FILE* outFile = fopen("magacin.out", "w");
fscanf(inFile, "%d%d", &n, &k);
for (int i = 1; i <= n; i++)
fscanf(inFile, "%d", &a[i]);
long long sum = 0;
for (int i = 1; i <= n; i++) {
r[i] = a[i] % k;
sum += a[i] / k;
}
// sortiramo niz ostataka counting sortom
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++)
c[ r[i] ]++;
for (int i = 1; i < k; i++)
c[i] = c[i] + c[i - 1];
for (int i = n; i >= 1; i--) {
sorted[ c[ r[i] ] ] = r[i];
c[ r[i] ]--;
}
int position = sum % n;
if (position == 0)
fprintf(outFile, "%d\n", sorted[n] - sorted[1]);
else
fprintf(outFile, "%d\n", sorted[position] + k - sorted[position + 1]);
fclose(inFile);
fclose(outFile);
return 0;
}
|
|
fajl: magacin.pas
|
const
MaxN = 1000100;
MaxK = 1000010;
var
inFile, outFile : text;
n, k, i, position : longint;
a, r, sorted : array[0..MaxN] of longint;
c : array[0..MaxK] of longint;
sum : int64;
begin
assign(inFile, 'magacin.in');
assign(outFile, 'magacin.out');
reset(inFile); rewrite(outFile);
readln(inFile, n, k);
for i := 1 to n do
read(inFile, a[i]);
sum := 0;
for i := 1 to n do begin
r[i] := a[i] mod k;
sum := sum + (a[i] div k);
end;
// sortiramo niz ostataka counting sortom
fillchar(c, sizeof(c), 0);
for i := 1 to n do
c[ r[i] ] := c[ r[i] ] + 1;
for i := 1 to k - 1 do
c[i] := c[i] + c[i - 1];
for i := n downto 1 do begin
sorted[ c[ r[i] ] ] := r[i];
c[ r[i] ] := c[ r[i] ] - 1;
end;
position := sum mod n;
if (position = 0) then
writeln(outFile, sorted[n] - sorted[1])
else
writeln(outFile, sorted[position] + k - sorted[position + 1]);
close(inFile);
close(outFile);
end.
|
|
|