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.

bombone.cpp    1,517 b      izvorni kod rešenja
bombone.pas    1,576 b      izvorni kod rešenja
bombone.tests.rar    91,147 b      test primeri
bombone.checker.cpp    486 b      izvorni kod programa za testiranje

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 ≤ ijn) 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.