|
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ć
|
|
|
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 ≤ i ≤ l-1), važi
xi = xi+1 ili
yi = yi+1 (susedi),
- ako je i ≠ j (1 ≤ i, j ≤
l), važi xi ≠ xj ili yi ≠ yj
(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;
}
|
|
|