|
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: Krtice
|
Dve grupe krtica su se našle na susednim stranicama pravougaone livade
oivičene ogradom. Svaka krtica je pronašla po jednu rupu na ogradi. U trenutku
kad je počela da pada kiša krtice su počele da kopaju tunele u pravcu normalnom
na ogradu. Krtica kopa tunel dok ne dođe na već iskopan tunel (svi tuneli su na
istoj dubini), a onda prestaje i počinje da se kreće već iskopanim tunelom. Ako
je data brzina kojom svaka krtica kopa tunel, izračunati koliko dugo će svaka
krtica kopati tunel pre nego što naiđe na već iskopan tunel. Ako neka krtica
nikada neće naići na iskopan tunel, ispisati -1.
Ulaz:
(Ulazni podaci se nalaze u datoteci krtice.in) U prvom redu datoteke
nalaze se dva cela broja: n1 - broj krtica u prvoj grupi (one
koje se nalaze na jednoj strani livade) i n2 - broj krtica u
drugoj grupi
(krtice koje se nalaze na drugoj strani livade) (0 < n1,
n2 < 5000). U sledećih
n1 redova se nalaze podaci o krticama iz prve grupe (u jednom redu su podaci o
jednoj krtici). U svakom redu se nalaze po dva realna broja koji označavaju
udaljenost krtice od ugla livade (na početku, pre nego što započne kopanje
kanala) i brzinu kojom ta krtica kopa tunel. U sledećih n2
redova se nalaze
podaci o krticama iz druge grupe. Udaljenosti i brzine su između 0 i 1000000.
Izlaz:
(Izlazne podatke upisati u datoteku krtice.out) U svakom od
n1 + n2
redova treba ispisati po jedan broj koji označava vreme koliko odgovarajuća
krtica (iz ulazne datoteke) sama kopa tunel. Vremena odgovaraju krticama po
redosledu kojim su navedene u ulazu, zaokruženo na dve decimale. Dozvoljena
greška je 0.01.
Primer:
krtice.in
|
|
krtice.out
|
2 3
1 4
2 5.1
4.5 3.6
1 1
5 0.5
|
|
4.50
0.88
-1.00
1.00
-1.00
|
Napomena:
Nije moguće da dve krtice stignu u istom trenutku kopajući tunele.
|
|
fajl: krtice.cpp
|
#include <algorithm>
#include <iostream>
#include <cstdlib>
#define TOLERANCIJA 0.01f
using namespace std;
typedef struct TKrtica {
double brzina;
double poz;
double vreme;
int id;
} Krtica;
bool porediPoPoziciji(const Krtica& left, const Krtica& right) {
return left.poz < right.poz;
}
bool porediPoId(const Krtica& left, const Krtica& right) {
return left.id < right.id;
}
int brojKrticaH;
int brojKrticaV;
Krtica* h;
Krtica* v;
void ulaz() {
freopen("krtice.in", "r", stdin);
freopen("krtice.out", "w", stdout);
scanf("%d %d", &brojKrticaV, &brojKrticaH);
v = (Krtica*) malloc(sizeof(Krtica) * brojKrticaV);
h = (Krtica*) malloc(sizeof(Krtica) * brojKrticaH);
for (int i=0; i<brojKrticaV; i++) {
scanf("%lf %lf", &v[i].poz, &v[i].brzina);
v[i].vreme = 0.0f;
v[i].id = i;
}
for (int i=0; i<brojKrticaH; i++) {
scanf("%lf %lf", &h[i].poz, &h[i].brzina);
h[i].vreme = 0.0f;
h[i].id = i;
}
}
void obrada() {
sort(h, h+brojKrticaH, porediPoPoziciji);
sort(v, v+brojKrticaV, porediPoPoziciji);
int nextV = 0;
int nextH = 0;
while (nextV < brojKrticaV || nextH < brojKrticaH) {
if (nextV == brojKrticaV) {
h[nextH++].vreme = -1.0;
} else if (nextH == brojKrticaH) {
v[nextV++].vreme = -1.0;
} else {
double tV = h[nextH].poz / v[nextV].brzina;
double tH = v[nextV].poz / h[nextH].brzina;
if (tV > tH) {
v[nextV++].vreme = tV;
} else if (tV < tH) {
h[nextH++].vreme = tH;
} else {
fprintf(
stderr,
"Nepravilan slucaj! Krtice %d i %d se susrecu u istom trenutku %lf!",
nextV, nextH, tV);
h[nextH].vreme = v[nextV].vreme = -1.0;
}
}
}
}
void izlaz() {
sort(h, h+brojKrticaH, porediPoId);
sort(v, v+brojKrticaV, porediPoId);
for (int i=0; i<brojKrticaV; i++)
printf("%lf\n", v[i].vreme);
for (int i=0; i<brojKrticaH; i++)
printf("%lf\n", h[i].vreme);
}
bool jednako(double a, double b) {
return (a + TOLERANCIJA > b) && (b + TOLERANCIJA > a);
}
void tester(const char* testovi) {
char ulaz[512];
char izlaz[512];
FILE* fTestovi = fopen(testovi, "r");
int count = 1;
while (!feof(fTestovi)) {
if (fscanf(fTestovi, "%s %s", ulaz, izlaz) <= 0)
break; // kraj testova
printf("Testiram za: Ulaz %s Izlaz: %s Rezultat: ", ulaz, izlaz);
try {
// pripremi ulaz
fclose(fopen("krtice.out", "w"));
FILE* fUlaz = fopen(ulaz, "r");
FILE* fKrticeIn = fopen("krtice.in", "w");
int ch;
while ((ch = fgetc(fUlaz)) != EOF) {
fputc(ch, fKrticeIn);
}
fclose(fKrticeIn);
fclose(fUlaz);
// pokreni program
system("krtice.exe");
// otvori izlaz programa i tacan izlaz
FILE* ispravno = fopen(izlaz, "r");
FILE* izlazPrograma;
try {
izlazPrograma = fopen("krtice.out", "r");
} catch (exception) {
fclose(ispravno);
throw "Greska kod otvaranja fajla";
}
// poredi izlaze programa
while (true) {
double a, b;
int fa, fb;
fa = fscanf(ispravno, "%lf", &a);
fb = fscanf(izlazPrograma, "%lf", &b);
if ( (fa <= 0 && fb > 0) || (fa > 0 && fb <= 0) ) {
throw "Razlicit EOF";
} else if (fa < 0 && fb < 0) {
break;
}
if (!jednako(a,b)) {
printf("\n%lf != %lf\n", a, b);
throw "Neispravan izlaz";
}
}
printf("OK %d\n", count++);
} catch (const char* exception) {
printf("FAILED\n");
printf("\tZASTO: %s\n", exception);
}
}
fclose(fTestovi);
}
int main(int argc, char** argv) {
if (argc == 1) {
ulaz();
obrada();
izlaz();
} else {
tester(argv[1]);
}
return 0;
}
|
|
|