|
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: Poruka
|
Mali Đurica kuca poruku na mobilnom telefonu. On je otkucao n
redova. Kada mali Đurica kaže da se kursor nalazi na poziciji
(i, j), to znači da se nalazi u i-tom redu iza j-tog znaka
- ako je j nula, to znači da je kursor na početku i-tog
reda. Malog Đuricu zanima koliko najmanje puta treba da pritisne
tastere gore, dole, levo, desno (koji služe za pomeranje kursora
kroz poruku) tako da od pozicije (sr, sc) stigne do pozicije
(fr, fc). Kursor sem pozicije sadrži i vrednost poslednje
pozicije u redu koja je dobijena pritiskom tastera levo ili desno,
čije će značenje detaljno biti opisano u nastavku problema.
Ovu vrednost ćemo zvati poslPoz.
Mali Đurica će Vam reći koliko redova ima u njegovoj
poruci i koliko je dugačak svaki red, tj. leni broj koji
predstavlja broj znakova u i-tom redu (odnosno dužinu i-tog
reda). On Vam takođe šalje na koji način funkcionišu njegovi
tasteri i njegov mobilni:
-
Sledeći red poslednjeg reda je prvi red; prethodni red
prvog reda je poslednji red, odnosno redovi su organizovani
ciklično. Prelaskom u sledeći, odnosno prethodni red, kursor
će se naći na poziciji koju pokazuje poslPoz u
skladu sa pravilom 8.
-
Pritiskom na taster dole kursor prelazi u sledeći red;
pritiskom na taster gore kursor prelazi u prethodni red.
-
Pritiskom na taster gore ili dole vrednost poslPoz se
ne menja.
-
Ako se kursor nalazi na početku reda r, pritiskom na
taster levo kursor prelazi na poziciju iza poslednjeg znaka
prethodnog reda i vrednost poslPoz se menja na vrednost
pozicije iza tog znaka.
-
Ako se kursor ne nalazi na početku reda r, tada pritiskom
na taster levo za pozicije (r, c), prelazi na (r, c-1), a
poslPoz postaje c-1.
-
Ako se kursor nalazi iza poslednjeg znaka reda r,
pritiskom na taster desno kursor prelazi na početak sledećeg
reda i vrednost poslPoz postaje 0.
-
Ako se kursor ne nalazi iza poslednjeg znaka reda r, tada
pritiskom na taster desno sa pozicije (r, c), prelazi na (r,
c+1), a poslPoz postaje c+1.
-
Ako se u nekom momentu kursor nađe u redu koji ima c
karaktera, a vrednost poslPoz je veća od c, tada
će kursor biti na poziciji c u tom redu. Vrednost
poslPoz SE NE MENJA u tom slučaju.
Ulaz:
(Ulazni podaci se nalaze u datoteci poruka.in) U prvom redu se nalazi prirodan broj n (1
≤ n ≤ 100). Potom se u n redova nalaze celi
brojevi leni (0 ≤ leni ≤ 100) koji redom
označavaju dužine redova. Zatim se u n+2-om redu nalaze
prirodni brojevi sr (1 ≤ sr ≤ n), sc (0
≤ sc ≤ lensr), fr (1 ≤ fr ≤
n) i fc (0 ≤ fc ≤ lenfr). Prva dva od tih
polja označavaju polaznu poziciju (redni broj vrste i kolone), a
druga dva završnu poziciju.
Izlaz:
(Izlazne podatke upisati u datoteku poruka.out) U izlaznu datoteku ispisati minimalni broj
pritisaka tastera da se od pozicije (sr, sc) dođe do pozicije
(fr, fc) koristeći navedena pravila.
- Maksimalno vreme izvršavanja programa je 0.2 sekunda.
Primer 1:
poruka.in
|
|
poruka.out
|
5
1
3
1
3
1
4 3 2 3
|
|
2
|
Objašnjenje.
Poruka bi mogla da izgleda ovako
X
XXX
X
XXX
X
a kursor se nalazi iza boldovanog slova. Pozicija je (4, 3), poslPoz ima vrednost 3. Tada
pritiskom gore kursor prelazi na kraj 3. reda i ima poziciju (3, 1), a poslPoz ostaje ista.
Ponovo pritiskom gore prelazi u 2. red, a kursor prelazi na poziciju u redu koju pokazuje
poslPoz i kursor se nalazi na željenoj poziciji.
Primer 2:
poruka.in
|
|
poruka.out
|
7
10
100
100
100
100
100
100
2 50 3 10
|
|
5
|
Objašnjenje.
Poruka bi mogla da izgleda ovako
XXXXXXXXXX
XX...XX - ukupno 100 znakova X
XX...XX - ukupno 100 znakova X
... - 6 redova, svaki sa 100 znakova X
XX...XX - ukupno 100 znakova X.
Pritiskom na taster gore kursor prelazi na (1, 10); poslPoz je 50. Pritiskom na taster
levo kursor prelazi na (1, 9); poslPoz postaje 9. Pritiskom na taster desno kursor prelazi
na poziciju (1, 10); poslPoz postaje 10. Pritiskom dva puta na taster dole kursor prelazi
na poziciju (2, 10), pa (3, 10).
|
|
fajl: poruka.cpp
|
/*
Drzavno takmicenje 2008
Zadatak: poruka
Autor: Slobodan Mitrovic, Deronje
Zadatak se resava obilaskom svih stanja u sirinu, odnosno primenom BFSa.
Svako stanje mozemo oznaciti sa (r, c, l) gde je (r, c) pozicija
kursora, a l vrednost promenljive poslPoz
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <fstream>
using namespace std;
int dp[100][101][101];
int main(){
ifstream fin("poruka.in");
ofstream fout("poruka.out");
int n;
fin >> n;
int a[n];
for (int i = 0; i < n; i++)
fin >> a[i];
int sr, sc, fr, fc;
fin >> sr >> sc >> fr >> fc;
sr--;
fr--;
queue <int> qr, qc, ql;
while (!qr.empty())
qr.pop();
while (!qc.empty())
qc.pop();
while (!ql.empty())
ql.pop();
memset(dp, 255, sizeof(dp));
dp[sr][sc][sc] = 0;
qr.push(sr); qc.push(sc); ql.push(sc);
int v[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int ret = 1 << 30;
while (!qr.empty()){
int r = qr.front(), c = qc.front(), l = ql.front();
if (r == fr && c == fc)
ret = min(ret, dp[r][c][l]);
qr.pop(); qc.pop(); ql.pop();
for (int i = 0; i < 4; i++){
int rr, cc, ll;
if (v[i][1] == 0){// idemo gore ili dole
rr = (r + v[i][0] + n) % n;
cc = ll = l;
cc = min(cc, a[rr]);
}
else{ // idemo levo ili desno
cc = ll = c + v[i][1];
rr = r;
if (cc > a[rr]){
rr = (rr + 1) % n;
cc = ll = 0;
}
else if (cc < 0){
rr = (rr - 1 + n) % n;
cc = ll = a[rr];
}
}
if (dp[rr][cc][ll] != -1)
continue;
dp[rr][cc][ll] = dp[r][c][l] + 1;
qr.push(rr); qc.push(cc); ql.push(ll);
}
}
fout << ret << endl;
fin.close();
fout.close();
return 0;
}
|
|
|