|
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ć
|
Sponzori
|
|
|
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.
|
|
|