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.

dolina.cpp    5,227 b      izvorni kod rešenja
dolina_256M.cpp    6,420 b      alternativno rešenje
dolina.tests.rar    43,490 b      test primeri
dolina.checker.cpp    1,695 b      izvorni kod programa za testiranje

zadatak: Dolina

Planinarski savez južne Srbije je odlučio da sagradi novu atrakciju na Staroj Planini. Po prvi put, svet će videti skijašku dolinu, stazu koja ide i nizbrdo i uzbrdo. Oni veruju da će skijaši dostići dovoljnu brzinu pri spustu, kako bi se popeli u drugom delu staze (pod uslovom da početna visina nije manja od krajnje). Da bi uživanje bilo što veće, potrebno je napraviti najdužu takvu stazu.

Da bi pojednostavili problem, Savez prestavlja teren matricom MxN polja, a visina svakog polja je poznata -- preuzeta iz Geografskog Instituta Srbije. Skijaška dolina je onda niz susednih polja, koja se ne ponavljaju, tako da visine polja prvo samo opadaju duž niza, a potom, počev od nekog polja, visine samo rastu do kraja niza. Dva polja su susedna ako dele zajedničku stranicu. Dužina skijaške doline je broj polja u tom nizu.

Matematički preciznije to možemo iskazati na sledeći način. Teren je matrica MxN polja, gde (i, j) predstavlja polje u i-tom redu i j-toj koloni, a h(i, j) je njegova visina. Skijaška dolina je niz (x1, y1), (x2, y2), ..., (xl, yl), takav da:

  • za svako i (1 ≤ il-1), važi xi = xi+1 ili yi = yi+1 (susedi),
  • ako je ij (1 ≤ i, j ≤ l), važi xixj ili yiyj (nema ponavljanja), i
  • postoji k (1 ≤ k ≤ l), tako da važi h(x1, y1) > h(x2, y2) > ... > h(xk-1, yk-1) > h(xk, yk) < h(xk+1, yk+1) < ... < h(xl, yl) (dole pa gore).
Dužina ove skijaške doline je l.

Planinarski Savez nema puno iskustva u programiranju, pa te je zamolio da napišeš program koji će naći najdužu skijašku dolinu zadatog terena. Ako postoji više skijaških dolina maksimalne dužine, možeš odabrati bilo koju.

Ulaz:

(Ulazni podaci se nalaze u datoteci dolina.in) Prvi red ulaza sadrži cele brojeve M i N, respektivno, razdvojene prazninom (1 ≤ M, N ≤ 70). U svakom od narednih M redova nalazi se N brojeva, tako da j-ti broj u i-tom redu predstavlja h(i, j). Visine polja su različiti celi brojevi u opsegu [-106, 106]. U svakoj liniji, brojevi su razdvojeni prazninom.

Izlaz:

(Izlazne podatke upisati u datoteku dolina.out) U prvi red izlaza potrebno je upisati broj lmax, najveću dužinu neke skijaške doline. U sledećih lmax linija dajte opis bilo koje skijaške doline te dužine, tako da se u i-tom redu nalaze dva cela broja xi i yi razdvojena prazninom, i (xi, yi) predstavlja i-to polje doline.

Primer 1:

dolina.in      dolina.out
3 4
2 6 7 16
1 4 3 20
9 8 17 12
        
9
3 1
3 2
2 2
2 1
1 1
1 2
1 3
1 4
2 4

Primer 2:

dolina.in      dolina.out
3 3
1 9 2
8 3 7
4 6 5
        
3
2 1
2 2
2 3
fajl: dolina.cpp
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define Nmax 70
#define Mmax 70

const int xMove[] = { -1, 1, 0, 0 };
const int yMove[] = { 0, 0, -1, 1 };

int field[Nmax][Mmax];  // visina polja
int sPos[Nmax][Mmax];  // pozicija polja u nizu polja sortiranih po visini
int N, M;

// indeksi polja
struct FieldPointer
{
  int x, y;

  FieldPointer(int xV, int yV)
  {
    x = xV;
    y = yV;
  }
};

bool operator<(FieldPointer fp1, FieldPointer fp2)
{
  return field[fp1.x][fp1.y] < field[fp2.x][fp2.y];
}

// podaci o paru polja:
// - indeksi prvog i drugog polja
// - duzina najduze doline koja se zavrsava ovim poljima
// - prethodni par polja preko koga se doslo do najboljeg resenja
struct FieldPair
{
  __int16 pathLength;
  __int8 move;

  FieldPair(int plV, int moveV)
  {
    pathLength = plV;
    move = moveV;
  }
};

vector<FieldPointer> sField;  // sortirani niz polja
vector<FieldPair> queuedPair;  // red parova polja u redosledu obilaska

int maxLength, maxPos;
vector<FieldPointer> downHill;  // polja na putu nadole
vector<FieldPointer> upHill;  // polja na putu nagore (u obrnutom redosledu)

void readInput(string fileName)
{
  ifstream inFile(fileName.c_str());
  inFile >> N >> M;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      inFile >> field[i][j];
  inFile.close();
}

void solve()
{
  int j, p1, p2, x1, y1, x2, y2, mVal, pl, pos1, pos2, pos, xp, yp, move, fieldp;

  // sortiranje polja po rastucoj visini
  for (int k = 0; k < N; k++)
    for (j = 0; j < M; j++)
      sField.push_back(FieldPointer(k, j));
  sort(sField.begin(), sField.end());
  // indeksiranje polja prema poziciji u sortiranom nizu
  for (int k = 0; k < (int)sField.size(); k++)
    sPos[sField[k].x][sField[k].y] = k;

  // *kreiranje reda parova polja*
  // Parovi polja se smestaju u red tako da za dva para polja pp1 i pp2 od kojih se pp1 pojavljuje u redu pre pp2 vazi:
  // - prvo polje u pp1 je na manjoj visini od prvog polja u pp2, ili
  // - drugo polje u pp1 je na majoj visini od drugog polja u pp2.
  // Time se obezbedjuje da, za svaki par polja, svi parovi preko kojih je moglo da se dodje su se ranije javili u redu
  // i resenje za njih je vec nadjeno.
  for (int k = 0; k < (int)sField.size(); k++)
    for (j = 0; j <= k; j++)
      queuedPair.push_back(FieldPair(-1, -1));

  // obilazak parova polja u redu
  for (int k = 0; k < (int)queuedPair.size(); k++)
  {
    // preuzimanje podataka o paru polja
    p1 = ((int)(sqrt((double)(8 * k + 1)) - 1)) / 2;
    p2 = k - p1 * (p1 + 1) / 2;
    x1 = sField[p1].x;
    y1 = sField[p1].y;
    x2 = sField[p2].x;
    y2 = sField[p2].y;
    mVal = field[x1][y1];
    
    // specijalni slucaj za par identicnih polja (pocetno polje)
    if ((x1 == x2) && (y1 == y2))
    {
      queuedPair[k].pathLength = 1;
      queuedPair[k].move = -1;
    }
    else
    {
      // pokusaj pomeranja prvog polja
      for (j = 0; j < 4; j++)
      {
        xp = x1 + xMove[j];
        yp = y1 + yMove[j];
        if ((xp >= 0) && (xp <= N - 1) && (yp >= 0) && (yp <= M - 1))
        {
          fieldp = field[xp][yp];
          if (fieldp < mVal)  // pomeranje je validno samo ako je novo polje na vecoj visini od oba kraja tekuce doline
                    // kako ne bi doslo do ponavljanja polja
          {
            pos1 = sPos[xp][yp];
            pos2 = sPos[x2][y2];
            if (fieldp < field[x2][y2])
              swap(pos1, pos2);
            pos = (pos1 * (pos1 + 1)) / 2 + pos2;

            pl = queuedPair[pos].pathLength;
            if (pl >= 1)
              if (pl + 1 > queuedPair[k].pathLength)
              {
                queuedPair[k].pathLength = pl + 1;
                queuedPair[k].move = j;
              }
          }
        }
      }
    }
  }

  // nalazenje duzine najduze doline i njenih krajnjih polja
  maxLength = 0;
  for (int k = 0; k < (int)queuedPair.size(); k++)
    if (queuedPair[k].pathLength > maxLength)
    {
      maxLength = queuedPair[k].pathLength;
      maxPos = k;
    }

  // rekonstrukcija doline
  pos = maxPos;
  p1 = ((int)(sqrt((double)(8 * pos + 1)) - 1)) / 2;
  p2 = pos - p1 * (p1 + 1) / 2;
  x1 = sField[p1].x;
  y1 = sField[p1].y;
  x2 = sField[p2].x;
  y2 = sField[p2].y;
  bool switched = false;
  move = queuedPair[pos].move;
  while (queuedPair[pos].move >= 0)
  {
    if (!switched)
      downHill.push_back(FieldPointer(x1, y1));
    else
      upHill.push_back(FieldPointer(x1, y1));
    x1 += xMove[move];
    y1 += yMove[move];
    if (field[x1][y1] < field[x2][y2])
    {
      switched = !switched;
      swap(x1, x2);
      swap(y1, y2);
    }
    pos1 = sPos[x1][y1];
    pos = (pos1 * (pos1 + 1)) / 2 + sPos[x2][y2];
    move = queuedPair[pos].move;
  }
  downHill.push_back(FieldPointer(x1, y1));  // pocetno polje, moze se smestiti u put nadole ili obrnuti put nagore
}

void writeOutput(string fileName)
{
  ofstream outFile(fileName.c_str());
  outFile << maxLength << endl;
  int i;
  for (i = 0; i < (int)downHill.size(); i++)
    outFile << downHill[i].x + 1 << " " << downHill[i].y + 1 << endl;
  for (i = (int)upHill.size() - 1; i >= 0; i--)
    outFile << upHill[i].x + 1 << " " << upHill[i].y + 1 << endl;

  outFile.close();
}

int main()
{
  readInput("dolina.in");
  solve();
  writeOutput("dolina.out");
  return 0;
}