|
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: 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;
}
|
|
|