Pokazivački opseg

Implementirati funkcije tako da rade na poluotvorenom pokazivačkom opsegu [pocetak, kraj) (nalik na opseg interatora [ begin(), end() )).

Zadaci:

long long zbir(const int* pocetak, const int* kraj) - računa zbir elemenata u opsegu [pocetak, kraj).
const int* najveci_element(const int* pocetak, const int* kraj) — vraća pokazivač na prvi maksimum, ili kraj ako je opseg prazan.
const int* nadji(const int* pocetak, const int* kraj, int x) — vraća pokazivač na prvi x, ili kraj ako ga nema.
void obrni(int* pocetak, int* kraj) — obrće niz u mestu.

Pitanja: Koja je alternativna vrednost koju funkcije najveci_element i nadji mogu da vrate? Kako se pokazivač koji vraća nadji pretvara u indeks? Zašto je obrni(a, a) bezbedno?

Ulaz

U prvom redu učitava se broj elemenata n $(1 \le n \le 1000)$. U drugom redu učitavase n elemenata niza. U trećem redu učitava se broj upita q, a u narednom redu i q upita.

Izlaz

Ispisati zbir svih elemenata. Ispisati indeks prvog maksimuma.

Za svaki upit x ispisati indeks njegovog prvog pojavljivanja (ili -1 ako ga nema), u obliku x -> i.

Na kraju podeliti niz na dve polovine, obrnuti svaku polovinu posebno i ispisati ceo niz nakon toga.

Primer

Ulaz

7
4 9 2 9 5 1 7
3
9 7 3

Izlaz

37
1
9 -> 1
7 -> 6
3 -> -1
2 9 4 7 1 5 9

Postavka

`main.cpp`

#include <iostream>
#include <algorithm>

namespace matf
{
  // TODO (1): implementirati zbir bez indeksiranja elemenata niza.
  long long zbir(const int* pocetak, const int* kraj)
  {
    return undefined;
  }

  // TODO (2): implementirati najveci_element bez indeksiranja
  // Vraca pokazivac na prvi najveci element, 
  // kraj ako je opseg prazan.
  const int* najveci_element(const int* pocetak, const int* kraj)
  {
    return undefined;
  }

  // TODO (3): implementirati nadji bez indeksiranja
  // pokazivac na prvi element jednak x, kraj ako ga nema.
  const int* nadji(const int* pocetak, const int* kraj, int x)
  {
    return undefined;
  }

  // TODO (4): implementirati obrni u mestu bez indeksiranja
  void obrni(int* pocetak, int* kraj)
  {
    return undefined;
  }

} // namespace matf

int main()
{
  int a[1000];
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];

  std::cout << matf::zbir(a, a + n) << std::endl;
  std::cout << matf::najveci_element(a, a + n) - a << std::endl;

  int q;
  std::cin >> q;
  for (int i = 0; i < q; ++i) {
    int x;
    std::cin >> x;
    const int* p = matf::nadji(a, a + n, x);
    std::cout << x << " -> " << (p == a + n ? -1 : p - a) << std::endl;
  }

  matf::obrni(a, a + n / 2);
  matf::obrni(a + n / 2, a + n);
  for (int i = 0; i < n; ++i)
    std::cout << ' ' << a[i];
  std::cout << std::endl;

  return 0;
}

Rešenje

`main.cpp`

#include <iostream>
#include <algorithm>

namespace matf
{
  // O(kraj - pocetak)
  long long zbir(const int* pocetak, const int* kraj)
  {
    long long s = 0;
    for (const int* p = pocetak; p != kraj; ++p)
      s += *p;
    return s;
  }

  // O(kraj - pocetak); pokazivac na prvi najveci element, kraj ako je opseg prazan.
  const int* najveci_element(const int* pocetak, const int* kraj)
  {
    if (pocetak == kraj)
      return kraj;
    const int* najveci = pocetak;
    for (const int* p = pocetak + 1; p != kraj; ++p)
      if (*p > *najveci)
        najveci = p;
    return najveci;
  }

  // O(kraj - pocetak); pokazivac na prvi element jednak x, kraj ako ga nema.
  const int* nadji(const int* pocetak, const int* kraj, int x)
  {
    for (const int* p = pocetak; p != kraj; ++p)
      if (*p == x)
        return p;
    return kraj;
  }

  // O(kraj - pocetak); obrce opseg u mestu, dva pokazivaca se krecu jedan ka drugom.
  void obrni(int* pocetak, int* kraj)
  {
    if (pocetak == kraj)
      return;

    --kraj;                        // sada kraj pokazuje na poslednji element
    while (pocetak < kraj) {
      std::swap(*pocetak, *kraj);
      ++pocetak;
      --kraj;
    }
  }

} // namespace matf

int main()
{
  int a[1000];
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];

  std::cout << matf::zbir(a, a + n) << std::endl;
  std::cout << matf::najveci_element(a, a + n) - a << std::endl;

  int q;
  std::cin >> q;
  for (int i = 0; i < q; ++i) {
    int x;
    std::cin >> x;
    const int* p = matf::nadji(a, a + n, x);
    std::cout << x << " -> " << (p == a + n ? -1 : p - a) << std::endl;
  }

  matf::obrni(a, a + n / 2);
  matf::obrni(a + n / 2, a + n);
  for (int i = 0; i < n; ++i)
    std::cout << ' ' << a[i];
  std::cout << std::endl;

  return 0;
}