|
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: Žetoni
|
Mika igra jednu, ne tako poznatu, kockarsku igru žetoni. Igra se sastoji u sledećem:
na početku, ispred njega se nalazi n gomila žetona u nizu, pri čemu je na i-toj gomili ai
žetona. Zatim Mika odigra određeni broj poteza, gde se pod jednim potezom podrazumeva
izbor dva broja i i j (i ≤ j) i dodavanje po jednog žetona
svim gomilama između i-te i j-te,
uključujući i ove dve gomile. Cilj igre je da, posle nekog broja poteza, na svim gomilama
bude tačno k žetona.
Kada se igra završi, igrač dobija žetone na osnovu broja odigranih poteza - šo manje
poteza, to više žetona. Odredite koliko je najmanje poteza potrebno da bi Mika završio
igru i možda ćete dobiti neke od Mikinih žetona.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke zetoni.in.)
U prvom redu ulazne datoteke nalaze se dva prirodna broja, n i k,
koji predstavljaju, redom, broj gomila i traženi broj
žetona na svakoj gomili na kraju igre (1 ≤ n ≤ 106, 1 ≤ k ≤ 109).
U narednom redu nalaze se n celih brojeva iz segmenta [0, k] - opis gomila.
Izlaz.
(Izlazni podaci se ispisuju u datoteku zetoni.out)
U prvom i jedinom redu izlazne datoteke ispisati jedan ceo broj -
najmanji broj poteza potrebnih da se završi igra. Koristiti 64-bitni tip podataka.
Primer 1.
zetoni.in
|
|
zetoni.out
|
4 5
2 1 3 1
|
|
6
|
Objašnjenje.Ukoliko sa [i, j] označimo dodavanje po
jednog žetona gomilama i, i + 1, ..., j, onda nizom od 6
poteza [2, 4], [4, 4], [4, 4], [1, 4], [1, 2], [1, 2] dobijamo po 5 žetona na
svakoj gomili, kao što je i trebalo. Ovo nije moguće postići u manje od 6
poteza.
Napomena. U 30% test primera je n ≤ 103.
|
|
fajl: zetoni.cpp
|
#include <cstdlib>
#include <cstdio>
#include <ctime>
const int MaxN = 1000100;
struct CoinPile
{
int num, left, right;
CoinPile(int n, int l, int r)
{
num = n; left = l; right = r;
}
CoinPile() {}
};
int n, k, x, pileNum, currIndex, nextIndex;
long long sol;
CoinPile coins[MaxN];
int main()
{
freopen("zetoni.in", "r", stdin);
freopen("zetoni.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &x);
coins[i] = CoinPile(x, i - 1, i + 1);
}
coins[0] = CoinPile(k + 1, 0, 1);
coins[n + 1] = CoinPile(k + 1, n, n + 1);
sol = -1;
currIndex = 1;
pileNum = n + 2;
while (pileNum > 2)
{
if (coins[ coins[currIndex].left ].num <= coins[ coins[currIndex].right ].num)
nextIndex = coins[currIndex].left;
else
nextIndex = coins[currIndex].right;
if (coins[nextIndex].num >= coins[currIndex].num)
{
sol += (coins[nextIndex].num - coins[currIndex].num);
pileNum--;
coins[ coins[currIndex].left ].right = coins[currIndex].right;
coins[ coins[currIndex].right ].left = coins[currIndex].left;
}
currIndex = nextIndex;
}
printf("%lld\n", sol);
return 0;
}
|
|
fajl: zetoni.pas
|
const
MaxN = 1000100;
var
inFile, outFile : text;
n, k, x, pileNum, currIndex, nextIndex, i : longint;
sol : int64;
num, left, right : array[0..MaxN] of longint;
BEGIN
assign(inFile, 'zetoni.in');
assign(outFile, 'zetoni.out');
reset(inFile); rewrite(outFile);
read(inFile, n, k);
for i := 1 to n do begin
read(inFile, num[i]);
left[i] := i - 1;
right[i] := i + 1;
end;
num[0] := k + 1; left[0] := 0; right[0] := 1;
num[n + 1] := k + 1; left[n + 1] := n; right[n + 1] := n + 1;
sol := -1;
currIndex := 1;
pileNum := n + 2;
while (pileNum > 2) do begin
if (num[ left[currIndex] ] <= num[ right[currIndex] ]) then
nextIndex := left[currIndex]
else
nextIndex := right[currIndex];
if (num[nextIndex] >= num[currIndex]) then begin
sol := sol + (num[nextIndex] - num[currIndex]);
pileNum := pileNum - 1;
right[ left[currIndex] ] := right[currIndex];
left[ right[currIndex] ] := left[currIndex];
end;
currIndex := nextIndex;
end;
writeln(outFile, sol);
close(inFile);
close(outFile);
END.
|
|
|