TAKMIČENJA IZ PROGRAMIRANJA


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.

magacin.cpp    977 b      izvorni kod rešenja
magacin.pas    1,118 b      izvorni kod rešenja
magacin.solution.pdf    41,341 b      rešenje problema
magacin.tests.7z    7,194,794 b      test primeri

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.