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.

nzd.cpp    1,331 b      izvorni kod rešenja
nzd.pas    1,118 b      izvorni kod rešenja
nzd.tests.rar    187,817 b      test primeri
nzd.checker.cpp    1,408 b      izvorni kod programa za testiranje

zadatak: NZD

Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve ai i ai + 1, niz (a1, a2, ..., ai, ai + 1, ... an) postaje (a1, a2, ..., ai + ai + 1, ... an). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).

Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.

Ulaz:

(Ulazni podaci se nalaze u datoteci nzd.in.) U prvom redu ulazne datoteke nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju (1 ≤ k < n ≤ 105). Sledeći red sadrži n prirodnih brojeva ai koji predstavljaju početni niz (ai ≤ 106). Suma svih brojeva nije veća od 106.

Izlaz:

(Izlazne podatke upisati u datoteku nzd.out) U prvom redu izlazne datoteke ispisati maksimalan moguć najveći zajednički delilac preostalih brojeva. U drugom redu izlazne datoteke ispisati k prirodnih brojeva - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

Primer:

nzd.in      nzd.out
6 3
12 7 3 2 15 15
        
6
12 12 30

Objašnjenje.

Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.

fajl: nzd.cpp
#include <cstdlib>
#include <cstdio>

const int MaxN = 100010;
const int MaxDivNum = 1010;

int n, k, s, divNum, groupCount, sol;
int a[MaxN], b[MaxN], divisors[MaxDivNum];

int main()
{
  FILE* inFile = fopen("nzd.in", "r");
  FILE* outFile = fopen("nzd.out", "w");

  fscanf(inFile, "%d%d", &n, &k);
  s = 0;
  for (int i = 0; i < n; i++)
  {
    fscanf(inFile, "%d", &a[i]);
    s += a[i];
  }
  
  divNum = 0;  // nalazimo sve delioce sume
  for (int i = 1; i <= s; i++)
  {
    if (s % i == 0)
      divisors[divNum++] = i;
  }

  for (int j = divNum - 1; j >= 0; j--)
  {
    sol = divisors[j]; // proveravamo da li j-ti delilac moze biti NZD
    groupCount = 0;
    for (int i = 0; i < n; i++) 
      b[i] = 0;

    for (int i = 0; i < n; i++)  // pravimo uzastopne grupe, prelazimo
    {               // na sledecu cim je suma deljiva sa sol
      b[groupCount] += a[i];
      if (b[groupCount] % sol == 0)
      {
        groupCount++;
      }
    }

    if (groupCount >= k)  // ako je broj grupa dovoljno veliki
    {
      break;
    }
  }

  // "spajamo" visak grupa u k-tu
  for (int i = k; i < groupCount; i++)
  {
    b[k - 1] += b[i];
  }

  fprintf(outFile, "%d\n", sol);
  for (int i = 0; i < k - 1; i++)
    fprintf(outFile, "%d ", b[i]);
  fprintf(outFile, "%d\n", b[k - 1]);

  fclose(inFile);
  fclose(outFile);
  return 0;
}
fajl: nzd.pas
CONST
  MaxN = 100010;
  MaxDivNum = 1010;

VAR
        inFile, outFile : TEXT;
  a, b : array[0..MaxN] of longint;
  divisors : array[0..MaxDivNum] of longint;
  n, k, s, divNum, groupCount, sol, i, j : longint;

BEGIN

  assign(inFile, 'nzd.in');
  assign(outFile, 'nzd.out');
  reset(inFile); rewrite(outFile);

  read(inFile, n, k);
  s := 0;
  for i := 1 to n do begin
    read(inFile, a[i]);
    s := s + a[i];
  end;

  divNum := 0;
  for i := 1 to s - 1 do
    if ((s MOD i) = 0) then begin
      divNum := divNum + 1;
      divisors[divNum] := i;
    end;
  
  for j := divNum downto 1 do begin
  
    sol := divisors[j];
    groupCount := 0;
    for i := 1 to n do b[i] := 0;
    
    for i := 1 to n do begin
      b[groupCount + 1] := b[groupCount + 1] + a[i];
      if ((b[groupCount + 1] MOD sol) = 0) then
        groupCount := groupCount + 1;
    end;
  
    if (groupCount >= k) then break;
  
  end;

  for i := k + 1 to groupCount do
    b[k] := b[k] + b[i];

  writeln(outFile, sol);
  for i := 1 to k - 1 do
    write(outFile, b[i], ' ');
  writeln(outFile, b[k]);

  close(inFile);
  close(outFile);

END.