|
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: Kredit
|
Profesor Đurić: Haloooo!
Draganče: Dobar dan, profesore, Draganče je ovde.
Profesor Đurić: šta raaadiš, momčino?
Draganče: Upravo šetam parkom, i kad sam stigao do fontane, dobio sam ideju za onaj
zadatak o kome smo juče diskutovali...
Profesor Đurić: A jeeee li.
Tako se nastavio telefonski razgovor, koji je trajao K minuta, i ko zna koliko bi još
trajao da Dragančetu nije nestalo kredita. Draganče je odmah krenuo da kupi dodatni
kredit, pošto zna lokacije svih trafika u parku, i krenuo je u onu do koje mu treba najmanje
vremena. čim stigne i uplati kredit, pozvaće profesora ponovo. Profesor Đurić želi
da kvalitetno organizuje svoje vreme i potrebna mu je procena koliko Dragančetu treba
vremena da ponovo pozove.
Ulaz:
(Ulazni podaci se nalaze u datoteci kredit.in) I Đurić i Draganče tačno znaju
mapu parka, koja je data u obliku pravougaone matrice dimenzija N x M, gde su N i M
brojevi zadati u prvom redu datoteke. U drugom redu je broj K. U svakom od narednih N
redova se nalazi po M znakova, koji označavaju polja na mapi. Dozvoljeni znakovi su 'F ', 'x ',
'. ' i 'T '. Znak 'F ' označava fontanu. Sve prepreke (npr. jezero, stadion, cveće...) označene
su sa 'x ', dok su sa '. ' označeni delovi parka slobodni za šetnju. Sa 'T ' su takođe označeni
delovi parka gde se može proći, i u njima se nalazi trafika gde se može uplatiti kredit.
Draganče se na početku razgovora nalazi kod fontane. U jednom minutu on može preći u
neko od susednih polja (istok, zapad, sever ili jug), a može ostati i tu gde jeste. U toku
razgovora on se šeta nasumično. Kada bude krenuo do trafike, neće praviti pauze, već ići
najkraćim putem dok ne stigne do nje.
Izlaz:
(Izlazne podatke upisati u datoteku kredit.out) Profesor Đurić ne zna gde se
Draganče šetao u toku razgovora i želi da proceni minimalno i maksimalno vreme koje
je potrebno Dragančetu da dođe do trafike sa kreditom. U jedinom redu izlazne datoteke
treba ispisati dva broja, MIN i MAX, odvojena razmakom; oni označavaju minimalni i
maksimalni broj minuta potreban da Draganče stigne do neke od trafika.
Ograničenja:
- brojevi N i M nisu veći od 200
- K nije veće od 500
- broj trafika nije veći od 1000
- znak '
F ' se nalazi tačno jednom u ulaznoj datoteci
- Park je takav da Draganče uvek može stići do neke od trafika. U delu sa fontanom se
ne nalazi trafika.
- vremensko ograničenje za izvršavanje programa je 1 s.
Napomena:
Ako je barem jedan od brojeva MIN ili MAX tačan, dobićete 50% poena za taj
primer.
Primer 1:
kredit.in
|
|
kredit.out
|
5 5
3
x..xF
.x...
T..x.
x.T..
...T.
|
|
2 5
|
Objašnjenje:
Posle 3 minuta razgovora, Draganče će moći da se približi nekoj od trafika
i za samo 2 minuta stigne do nje, a moguće je i da ostane sve vreme kraj fontane, odakle će
mu trebati 5 minuta do najbliže trafike.
|
|
fajl: kredit.cpp
|
#include <stdio.h>
#include <vector>
using namespace std;
FILE* fin, *fout;
int n, m, k;
char a[200][200];
int startx, starty, n_trafika;
void input() {
char c;
fin = fopen("kredit.in", "r");
fscanf(fin, "%d%d%d%c", &n, &m, &k, &c);
for (int i = 0; i < n; i++)
fscanf(fin, "%s", &a[i]);
fclose(fin);
}
void init() {
input();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (a[i][j] == 'F') {
startx = i; starty = j;
}
}
}
bool in(int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 'X');
}
void bfs(vector<pair<int, int> > start, int dist[][200], int limit) {
vector<pair<int, int> > next, now(start);
for (int i = 0; i < now.size(); i++)
dist[now[i].first][now[i].second] = 0;
for (int i = 0; i < limit && !now.empty(); i++) {
for (int j = 0; j < now.size(); j++) {
pair<int, int> pos = now[j];
int x = pos.first, y = pos.second;
if (in(x+1, y))
if (dist[x+1][y]==-1) {
next.push_back(make_pair(x+1,y));
dist[x+1][y] = i+1;
}
if (in(x-1, y))
if (dist[x-1][y]==-1) {
next.push_back(make_pair(x-1,y));
dist[x-1][y] = i+1;
}
if (in(x, y+1))
if (dist[x][y+1]==-1) {
next.push_back(make_pair(x,y+1));
dist[x][y+1] = i+1;
}
if (in(x, y-1))
if (dist[x][y-1]==-1) {
next.push_back(make_pair(x,y-1));
dist[x][y-1] = i+1;
}
}
now.clear();
next.swap(now);
}
}
void output(int min, int max) {
fout = fopen("kredit.out", "w");
fprintf(fout, "%d %d\n", min, max);
fclose(fout);
}
int main(int argc, char *argv[])
{
init();
int dist1[n][200], dist2[n][200];
vector<pair<int, int> > s;
s.push_back(make_pair(startx, starty));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
dist1[i][j] = -1;
bfs(s, dist1, k);
vector<pair<int, int> > t;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
dist2[i][j] = -1;
if (a[i][j] == 'T')
t.push_back(make_pair(i, j));
}
bfs(t, dist2, 1000000);
int max = 0, min = 1000000;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (dist1[i][j] != -1) {
if (dist2[i][j] > max)
max = dist2[i][j];
if (dist2[i][j] < min)
min = dist2[i][j];
}
output(min, max);
return 0;
}
|
|
|