|
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: Bombone
|
Mali Đole je u izlogu prodavnice slatkiša ugledao n bombona. Bombone su poređane
u niz i svaka je predstavljena jednim prirodnim brojem - različiti brojevi označavaju da
se radi o različitim vrstama bombona, a isti brojevi označavaju iste vrste bombona. On
planira da zgrabi neke od bombona, eventualno plati i kasnije se zasladi.
Radi dobitka na brzini, on želi da zgrabi samo neki uzastopni podniz bombona, tj. da
izabere indekse i, j (1 ≤ i ≤ j ≤ n) i da pokupi sve
bombone koje se nalaze na pozicijama i, i + 1,..., j - 1, j.
Takođe, pošto ne voli raznolikost, u tom podnizu ne sme biti više od 3 različite vrste bombona .
Npr. podniz 12434 nije dobar jer sadrži 4 vrste bombona.
Odrediti na koliko načina mali Đole može da se zasladi.
Ulaz.
(Ulazni podaci se uqitavaju iz datoteke bombone.in)
U prvom redu ulazne datoteke nalazi se jedan prirodan broj n koji predstavlja broj
bombona u izlogu (1 ≤ n ≤ 105 ). U sledećem redu se nalaze n prirodnih brojeva
(ne većih od 109) koji predstavljaju odgovarajiće vrste bombona.
Izlaz.
(Izlazni podaci se ispisuju u datoteku bombone.out)
U prvom i jedinom redu izlazne datoteke ispisati broj uzastpnih podnizova bombona u
kojima se pojavljuju najviše 3 različite vrste.
Primer 1.
bombone.in
|
|
bombone.out
|
5
1 2 4 3 4
|
|
13
|
Objašnjenje. Imamo 13 mogućih podnizova sa traženom osobinom: (12434)
(12434) (12434)
(12434) (12434)
(12434) (12434)
(12434) (12434)
(12434) (12434)
(12434) i (12434)
Primer 2.
bombone.in
|
|
bombone.out
|
6
10 20 10 30 20 20
|
|
21
|
Objašnjenje. Kako ukupno imamo samo 3 različite vrste bombona (10, 20 i 30), svaki uzastopni
podniz (a njih ima 21) zadovoljava uslove.
Napomena.
U 20% test primera je n ≤ 100.
U 50% test primera je n ≤ 1000.
|
|
fajl: bombone.cpp
|
#include <cstdlib>
#include <cstdio>
const int MaxN = 100010;
struct Candy
{
int type;
int num;
};
int n, differentNum;
int a[MaxN];
Candy B[4];
long long sol;
// da li postoji data vrsta bombona medju trenutnim
int find(int type)
{
for (int i = 1; i <= 3; i++)
if (B[i].type == type)
return i;
return -1;
}
// naci slobodno mesto da ubacimo trenutnu vrstu
int freeIndex()
{
for (int i = 1; i <= 3; i++)
if (B[i].num == 0)
return i;
}
int main()
{
freopen("bombone.in", "r", stdin);
freopen("bombone.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
differentNum = 0;
for (int i = 1; i <= 3; i++)
{
B[i].type = 0;
B[i].num = 0;
}
sol = 0;
int left = 1;
for (int right = 1; right <= n; right++)
{
int ind = find(a[right]); // da li vrsta a[right] vec postoji
if (ind != -1) // ako da, povecati brojac
{
B[ind].num++;
}
else
{
if (differentNum == 3) // ako ne postoji i imamo 3 razlicite vrste, moramo da izbacujemo
{
while (differentNum == 3)
{
ind = find(a[left]);
B[ind].num--;
left++;
if (B[ind].num == 0)
{
B[ind].type = 0;
differentNum--;
}
}
}
ind = freeIndex(); // ubaciti tip a[right] na jedno od 3 slobodna mesta
B[ind].type = a[right];
B[ind].num = 1;
differentNum++;
}
sol += (right - left + 1);
}
printf("%lld\n", sol);
return 0;
}
|
|
fajl: bombone.pas
|
const
MaxN = 100010;
var
inFile, outFile : text;
n, differentNum, i, left, right, ind : longint;
Kind, Num : array[0..3] of longint;
a : array[0..MaxN] of longint;
sol : int64;
// da li postoji data vrsta bombona medju trenutnim
function find(x : longint) : longint;
begin
find := -1;
for i := 1 to 3 do
if (x = Kind[i]) then find := i;
end;
// naci slobodno mesto da ubacimo trenutnu vrstu
function freeIndex : longint;
begin
for i := 1 to 3 do
if (Num[i] = 0) then freeIndex := i;
end;
BEGIN
assign(inFile, 'bombone.in');
assign(outFile, 'bombone.out');
reset(inFile); rewrite(outFile);
read(inFile, n);
for i := 1 to n do read(inFile, a[i]);
differentNum := 0;
for i := 1 to 3 do begin
Kind[i] := 0;
Num[i] := 0;
end;
sol := 0;
left := 1;
for right := 1 to n do begin
ind := find(a[right]); // da li vrsta a[right] vec postoji
if (ind <> -1) then Num[ind] := Num[ind] + 1 // ako da, povecati brojac
else begin
if (differentNum = 3) then // ako ne postoji i imamo 3 razlicite vrste, moramo da izbacujemo
while (differentNum = 3) do begin
ind := find(a[left]);
Num[ind] := Num[ind] - 1;
left := left + 1;
if (Num[ind] = 0) then begin
Kind[ind] := 0;
differentNum := differentNum - 1;
end;
end;
ind := freeIndex;
Kind[ind] := a[right];
Num[ind] := 1;
differentNum := differentNum + 1;
end;
sol := sol + (right - left + 1);
end;
writeln(outFile, sol);
close(inFile);
close(outFile);
END.
|
|
|