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.

poruka.cpp    1,718 b      izvorni kod rešenja
poruka.tests.rar    1,919 b      test primeri

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:

  1. 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.
  2. Pritiskom na taster dole kursor prelazi u sledeći red; pritiskom na taster gore kursor prelazi u prethodni red.
  3. Pritiskom na taster gore ili dole vrednost poslPoz se ne menja.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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 ≤ srn), sc (0 ≤ sclensr), fr (1 ≤ frn) i fc (0 ≤ fclenfr). 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;
}