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.

mornar.cpp    1,815 b      izvorni kod rešenja
mornar.checker.rar    103,440 b      program za testiranje
mornar.tests.rar    545,011 b      test primeri

zadatak: Mornar Đura

Mornar Đura je veliki avanturista i nakon završene karijere, odlučio je da krene na put oko sveta. Krenuo je iz svog rodnog mesta, obišao veliki broj gradova i na kraju se vratio kući. Pošto je Đura čovek u penziji, počeo je da zaboravlja. Želeo je da rekonstruiše redosled gradova koje je posećivao, međutim, sve što mu je ostalo su bile autobuske, avionske i karte za brodove kojima se prevozio. Pomozite Đuri da rekonstruiše svoje putešestvije koje će prepričavati unucima.

Na svakoj karti se nalazi ime kompanije koja prevozi, ime polazišta i odredišta. Poznato je da Đura, avanturista u duši, nikada ne posećuje isti grad dva puta (ako to nije njegov rodni grad, naravno).

Ulaz:

U prvom redu tekstualne datoteke mornar.in se nalazi broj karata koje je Đura prikupio posle putovanja (N ≤ 20000), a nakon toga, posle razmaka, sledi ime Đurinog rodnog grada. U narednih N redova sledi opis svake od karata. Svaki red je zapisan na sledeći način:

Ime1:Ime2->Ime3

Ime1 je ime kompanije, Ime2 je ime polaznog grada, dok je Ime3 destinacija. Svako ime (uključujući i ime rodnog grada) se sastoji isključivo od slova engleskog alfabeta. Prvo slovo imena je veliko, dok su ostala mala. Redosled pojavljivanja karata u ulazu ne mora biti isti kao i redosled kojim je Đura putovao.

Izlaz:

U prvom i jedinom redu izlazne datoteke mornar.out ispisati N+1 ime, tako što će prvo i poslednje ime biti ime Đurinog rodnog grada. Između svaka dva imena obavezno staviti ,,->''. Ne treba dodavati razmake, niti druge znakove.

Primer:

mornar.in      mornar.out
5 Nis
Jato:Beograd->Nis
Soko:Cuprija->Jagodina
Espreso:Nis->Aleksinac
Simpleks:Jagodina->Beograd
Raketla:Aleksinac->Cuprija
        
Nis->Aleksinac->Cuprija->Jagodina->Beograd->Nis
rešenje


Najpre ćemo sortirati karte po leksikografskom uređenju mesta polazišta. Posle toga, krećemo od Đurinog rodnog grada i ponavljamo postupak kojim tražimo sledeći grad, sve dok se ne vratimo u rodni grad. Da bismo našli koja je naredna destinacija, dovoljno je da u skupu karata pronađemo kartu u kojoj je tekući grad polazište. Pošto su nam karte sortirane prema mestu polaska, to ćemo najbrže pronaći binarnom pretragom.

Pseudokod

SORT-KARTE
current = NEXT(start)				//start je rodni grad
OUTPUT(start, "->")
WHILE start != current
	OUTPUT(current, "->")
	current = NEXT(current)
OUTPUT(start)

Složenost ovog algoritma je O(Nlog(N)). To je složenost sortiranja. Osim toga, program će proći kroz petlju N puta, dok u svakom prolasku kroz petlju izvrši jednu binarnu pretragu čija je složenost logaritamskog reda.

fajl: mornar.cpp
#include <stdlib.h>
#include <cstdlib>
#include <fstream>


using namespace std;

#define MAXN 20005
#define MAXL 20


typedef struct{
        char s[MAXL];
        char d[MAXL];
} karta;

int n;
karta t[MAXN];

// ucitavanje imena
// Najpre se propustaju svi karakteri dok se ne dodje do velikog slova, a potom se ucita ime
void ucitaj(char* ss, ifstream &in){
      char c = 'a';
      int i = 0;
      while (c < 'A' || c > 'Z') in >> c;
      do {
            ss[i++] = c;
            in >> c;
            if (in.eof()) break;
      } while (c >= 'a' && c <= 'z');
      in.putback(c);
      ss[i] = 0;
}

// funkcija koju koristi quick sort za poredjenje
int uporedi_karte(const void* k1, const void* k2){
    karta* a = (karta*) k1;
    karta* b = (karta*) k2;
    return strcmp(a->s, b->s);
}

// pronalazi indeks karte sa datim polaznim mestom
// vrsi se binarna pretraga
int pronadji(char* s){
    int l = 0, d = n, m;
    while (1){
          if (l == d) return l;
          m = (l + d)/2;
          int x = strcmp(t[m].s,s);
          if (x > 0) d = m-1;
          else if (x < 0) l = m+1;
          else return m;
    }
}

int main(int argc, char *argv[])
{
    ifstream in("mornar.in");
    ofstream out("mornar.out");

    char start[MAXL], pom[MAXL];
    int i;
    in >> n;
    ucitaj(start, in);
    for (i = 0; i < n; i++){
        ucitaj(pom, in);
        ucitaj(t[i].s, in);
        ucitaj(t[i].d, in);
    }
    qsort(t, n, sizeof(karta), uporedi_karte);
    char *s;
    s = start;
    do{
       out << s << "->";
       int i = pronadji(s);
       s = t[i].d;                       
    } while  (strcmp((char*)start, s));
    out << start << endl;
    in.close();
    out.close();
    return EXIT_SUCCESS;
}