Uređena kolekcija

Implementirati tip podataka UredjenaKolekcija koji predstavlja isti apstraktni tip kao NeuredjenaKolekcija (multiskup celih brojeva), ali se elementi čuvaju u nizu u neopadajućem redosledu.

Reprezentacija: velicina je trenutni broj elemenata; elementi se čuvaju u nizu elementi na pozicijama 0 .. velicina - 1, sortirano neopadajuće; KAPACITET niza je fiksan.

Operacije:

bool invarijanta_vazi(const UredjenaKolekcija& k) — vraća true tačno kada invarijanta važi.
std::size_t prva_ne_manja(const UredjenaKolekcija& k, int x) — najmanja pozicija i takva da je k.elementi[i] >= x; k.velicina ako takva pozicija ne postoji.
void dodaj(UredjenaKolekcija& k, int x) — dodaje jedno pojavljivanje x, čuvajući sortiranost. Preduslov: k.velicina < KAPACITET.
bool sadrzi(const UredjenaKolekcija& k, int x) — vraća true ako se x nalazi u kolekciji, bar jednom.
void obrisi(UredjenaKolekcija& k, int x) — uklanja jedno pojavljivanje x, ako postoji; u suprotnom ne radi ništa.
std::size_t broj_pojavljivanja(const UredjenaKolekcija& k, int x) — broj pojavljivanja x u kolekciji.
void ispisi(const UredjenaKolekcija& k) — ispisuje sve elemente, u sortiranom redosledu.

Zadaci:

Definisati invarijantu strukture, kao komentar, i implementirati invarijanta_vazi. Pozvati assert(invarijanta_vazi(k)) na kraju dodaj i obrisi. Šta ova funkcija ne može da proveri?
Implementirati prva_ne_manja binarnom pretragom, bez std::lower_bound.
Implementirati sadrzi, dodaj, obrisi.
Implementirati broj_pojavljivanja u logaritamskoj slozenosti.
Odrediti najgoru vremensku složenost implementiranih funkcija.

Ulaz

U prvom redu se učitava broj upita $q$ $(1 \le q \le 1000)$. Kapacitet kolekcije je $1000$.

Svaki od narednih $q$ redova sadrži jedan od upita:

D x — dodaj(k, x) $(-10^9 \le x \le 10^9)$
B x — obrisi(k, x)
S x — sadrzi(k, x)
P x — broj_pojavljivanja(k, x)
V — k.velicina
I — ispisi(k)

Garantovano je da broj upita tipa D ne prelazi KAPACITET.

Izlaz

Za upit S x ispisati DA ako kolekcija sadrži x, ili NE u suprotnom.

Za upit P x ispisati broj pojavljivanja x u kolekciji.

Za upit V ispisati trenutan broj elemenata.

Za upit I ispisati, u jednom redu, sve elemente kolekcije u sortiranom (neopadajućem) redosledu, razdvojene razmakom. Ako je kolekcija prazna ispisati samo novi red.

Upiti D i B ne proizvode izlaz.

Primer

Ulaz

21
D 12
D 4
D 9
D 4
D 17
D 6
I
V
S 9
S 8
B 12
I
B 4
V
S 4
B 4
V
S 4
B 100
V
I

Izlaz

4 4 6 9 12 17
6
DA
NE
4 4 6 9 17
4
DA
3
NE
3
6 9 17

Postavka

`uredjena_kolekcija.hpp`

#ifndef UREDJENA_KOLEKCIJA_HPP
#define UREDJENA_KOLEKCIJA_HPP

#include <cstddef>

namespace matf
{
  const std::size_t KAPACITET = 1000;

  struct UredjenaKolekcija {
    int elementi[KAPACITET];
    std::size_t velicina = 0;
    // TODO (1): napisati invarijantu ovde, kao komentar
  };

  bool invarijanta_vazi(const UredjenaKolekcija& k);

  std::size_t prva_ne_manja(const UredjenaKolekcija& k, int x);

  void dodaj(UredjenaKolekcija& k, int x);
  bool sadrzi(const UredjenaKolekcija& k, int x);
  void obrisi(UredjenaKolekcija& k, int x);

  std::size_t broj_pojavljivanja(const UredjenaKolekcija& k, int x);

  void ispisi(const UredjenaKolekcija& k);

} // namespace matf

#endif // UREDJENA_KOLEKCIJA_HPP

`uredjena_kolekcija.cpp`

#include "uredjena_kolekcija.hpp"

#include <cassert>
#include <iostream>

namespace matf
{
  // TODO (1): implementirati invarijanta_vazi
  bool invarijanta_vazi(const UredjenaKolekcija& k) 
  {
    return undefined;
  }

  // najmanji indeks i takav da je k.elementi[i] >= x; k.velicina ako takav ne postoji
  // TODO (2): implementirati prva_ne_manja binarnom pretragom (bez std::lower_bound)
  std::size_t prva_ne_manja(const UredjenaKolekcija& k, int x)
  {
    return undefined;
  }

  // preduslov: k.velicina < KAPACITET
  // TODO (3): implementirati dodaj
  void dodaj(UredjenaKolekcija& k, int x)
  {
    return undefined;
  }

  // TODO (3): implementirati dodaj
  bool sadrzi(const UredjenaKolekcija& k, int x)
  {
    return undefined;
  }

  // TODO (3): implementirati obrisi
  void obrisi(UredjenaKolekcija& k, int x)
  {
    return undefined;
  }

  // TODO (4): napisati najgoru vremensku slozenost svake funkcije, kao komentar

  // TODO (5): implementirati broj_pojavljivanja u logaritamskoj slozenosti
  std::size_t broj_pojavljivanja(const UredjenaKolekcija& k, int x)
  {
    return undefined;
  }

  void ispisi(const UredjenaKolekcija& k)
  {
    for (std::size_t i = 0; i < k.velicina; ++i)
      std::cout << k.elementi[i] << ' ';
    std::cout << '\n';
  }

} // namespace matf

`main.cpp`

#include "uredjena_kolekcija.hpp"

#include <iostream>

int main()
{
  int q;
  std::cin >> q;

  matf::UredjenaKolekcija k;
  while (q--) {
    char op;
    std::cin >> op;
    if (op == 'D') {
      int x;
      std::cin >> x;
      matf::dodaj(k, x);
    } else if (op == 'B') {
      int x;
      std::cin >> x;
      matf::obrisi(k, x);
    } else if (op == 'S') {
      int x;
      std::cin >> x;
      std::cout << (matf::sadrzi(k, x) ? "DA" : "NE") << '\n';
    } else if (op == 'P') {
      int x;
      std::cin >> x;
      std::cout << matf::broj_pojavljivanja(k, x) << '\n';
    } else if (op == 'V') {
      std::cout << k.velicina << '\n';
    } else if (op == 'I') {
      matf::ispisi(k);
    }
  }

  return 0;
}

Rešenje

`uredjena_kolekcija.hpp`

#ifndef UREDJENA_KOLEKCIJA_HPP
#define UREDJENA_KOLEKCIJA_HPP

#include <cstddef>

namespace matf
{
  const std::size_t KAPACITET = 1000;

  struct UredjenaKolekcija {
    int elementi[KAPACITET];
    std::size_t velicina = 0;
    // invarijanta: 0 <= velicina <= KAPACITET,
    // niz elementi sadrzi elemente kolekcije na pozicijama 0 .. velicina - 1, i
    // elementi[i] <= elementi[i + 1] za svako 0 < i + 1 < velicina
  };

  bool invarijanta_vazi(const UredjenaKolekcija& k);
  std::size_t prva_ne_manja(const UredjenaKolekcija& k, int x);
  void dodaj(UredjenaKolekcija& k, int x);
  bool sadrzi(const UredjenaKolekcija& k, int x);
  void obrisi(UredjenaKolekcija& k, int x);
  std::size_t broj_pojavljivanja(const UredjenaKolekcija& k, int x);
  void ispisi(const UredjenaKolekcija& k);

} // namespace matf

#endif // UREDJENA_KOLEKCIJA_HPP

`uredjena_kolekcija.cpp`

#include "uredjena_kolekcija.hpp"

#include <cassert>
#include <iostream>

namespace matf
{

  // O(velicina);
  // Kolekcija ostaje nepromenjena zbog const&, pa invarijanta vazi.
  bool invarijanta_vazi(const UredjenaKolekcija& k)
  {
    if (k.velicina > KAPACITET)
      return false;
    for (std::size_t i = 0; i + 1 < k.velicina; ++i)
      if (k.elementi[i] > k.elementi[i + 1])
        return false;
    return true;
  }

  // O(log velicina)
  // Kolekcija ostaje nepromenjena zbog const&, pa invarijanta vazi.
  std::size_t prva_ne_manja(const UredjenaKolekcija& k, int x)
  {
    std::size_t l = 0, d = k.velicina;   // odgovor je u [l, d]
    while (l < d) {
      std::size_t m = l + (d - l) / 2;
      if (k.elementi[m] < x)
        l = m + 1;
      else
        d = m;
    }
    return l;
  }

  // O(velicina), zbog pomeranja elemenata
  // Invarijanta vazi jer se x ubacuje tacno na mesto gde ostaje sortiranost
  // (prva_ne_manja daje prvu poziciju sa vrednoscu >= x), a ostali elementi
  // samo menjaju mesto, bez promene vrednosti.
  void dodaj(UredjenaKolekcija& k, int x)
  {
    assert(k.velicina < KAPACITET);
    std::size_t poz = prva_ne_manja(k, x);
    for (std::size_t i = k.velicina; i > poz; --i)
      k.elementi[i] = k.elementi[i - 1];
    k.elementi[poz] = x;
    ++k.velicina;
    assert(invarijanta_vazi(k));
  }

  // O(log velicina)
  // Kolekcija ostaje nepromenjena zbog const&, pa invarijanta vazi.
  bool sadrzi(const UredjenaKolekcija& k, int x)
  {
    std::size_t poz = prva_ne_manja(k, x);
    return poz < k.velicina && k.elementi[poz] == x;
  }

  // O(velicina), zbog pomeranja elemenata
  // Invarijanta vazi i kada se ne pronadje x (kolekcija nepromenjena), i kada
  // se pronadje i obrise (preostali elementi ostaju sortirani, jer su samo
  // pomereni, bez promene relativnog redosleda).
  void obrisi(UredjenaKolekcija& k, int x)
  {
    std::size_t poz = prva_ne_manja(k, x);
    if (poz == k.velicina || k.elementi[poz] != x)
      return;
    for (std::size_t i = poz; i + 1 < k.velicina; ++i)   // levo na desno
      k.elementi[i] = k.elementi[i + 1];
    --k.velicina;
    assert(invarijanta_vazi(k));
  }

  // O(log velicina)
  // Pretpostavlja x < INT_MAX (puca za x == INT_MAX, zbog x + 1).
  std::size_t broj_pojavljivanja(const UredjenaKolekcija& k, int x)
  {
    return prva_ne_manja(k, x + 1) - prva_ne_manja(k, x);
  }

  // O(velicina)
  void ispisi(const UredjenaKolekcija& k)
  {
    for (std::size_t i = 0; i < k.velicina; ++i)
      std::cout << k.elementi[i] << ' ';
    std::cout << std::endl;
  }

} // namespace matf

`main.cpp`

#include "uredjena_kolekcija.hpp"

#include <iostream>

int main()
{
  int q;
  std::cin >> q;

  matf::UredjenaKolekcija k;
  while (q--) {
    char op;
    std::cin >> op;
    if (op == 'D') {
      int x;
      std::cin >> x;
      matf::dodaj(k, x);
    } else if (op == 'B') {
      int x;
      std::cin >> x;
      matf::obrisi(k, x);
    } else if (op == 'S') {
      int x;
      std::cin >> x;
      std::cout << (matf::sadrzi(k, x) ? "DA" : "NE") << std::endl;
    } else if (op == 'P') {
      int x;
      std::cin >> x;
      std::cout << matf::broj_pojavljivanja(k, x) << std::endl;
    } else if (op == 'V') {
      std::cout << k.velicina << std::endl;
    } else if (op == 'I') {
      matf::ispisi(k);
    }
  }

  return 0;
}