|
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: Autoput
|
Vlada zemlje Bajtovije je odlučila da poboljša infrastrukturu puteva izgradnjom novog autoputa. Autoput ima oblik prave linije, koja je paralelna sa Y osom. Dužina puta može biti proizvoljno velika. Cilj izgradnje novog puta je da on bude dostupan što većem broju građana te zemlje. Poznato je da će žitelji određenog grada koristiti autoput ako najkraće rastojanje od njihovog grada do tog puta nije veće od graničnog rastojanja D.
Ulaz:
U prvom redu datoteke autoput.in se nalazi broj gradova u Bajtoviji, N ≤ 50000 i broj D, koji su razdvojeni razmakom. U narednih N redova sledi opis svakog grada koji čine tri broja razdvojena razmakom. Najpre su upisane koordinate X i Y, a potom sledi broj žitelja tog grada. Svi brojevi u datoteci su prirodni i manji od 100000.
Izlaz:
U prvom i jedinom redu izlazne datoteke autoput.out ispisati maksimalan broj stanovnika Bajtovije koji će koristiti autoput. Garantuje se da taj broj neće preći dve milijarde.
Primer:
autoput.in
|
|
autoput.out
|
5 2
11 9 1000
2 5 2000
7 5 10000
5 8 1000
9 2 5000
|
|
16000
|
Objašnjenje:
Autoput će biti prava X=7, tako da će biti dostupan trećem, četvrtom i petom gradu iz ulaza.
|
|
rešenje
|
Najpre ćemo sortirati gradove prema X koordinatama. Zatim, krenuvši sa leve na desnu stranu, vodimo računa o intervalu koji je manji ili jednak 2D. Kako novi grad ,,uđe'' u interval, tako trenutnoj sumi dodajemo broj stanovnika grada, a kada grad više nije u intervalu, onda smanjimo sumu za njegov broj stanovnika. U svakom trenutku proveravamo da li trenutna suma prevazilazi maksimalnu sumu.
Pseudokod
SORT-GRADOVI
l = 0
max = 0
FOR d = 0 to n-1
WHILE x[d] - x[l] > 2D
l++
sum = sum - s[l]
sum += s[d]
IF sum > max THEN
max = sum
RETURN max
Složenost ovog algoritma je O(Nlog(N)). To je složenost sortiranja. Složenost petlje je linearna zbog toga što ukupan broj iteracija kroz WHILE petlju ne može da pređe N.
|
|
fajl: autoput.cpp
|
#include <cstdlib>
#include <fstream>
#include <stdlib.h>
using namespace std;
#define MAX 50005
// x i y su koordinate, a z je broj stanovnika
typedef struct{
int x, y, z;
} city;
// koristi se za uporedjivanje gradova po x koordinati
// zbog quick sorta
int up(const void *px, const void* py){
city* a = (city*) px;
city* b = (city*) py;
if (a->x < b->x) return -1;
if (a->x > b->x) return 1;
return 0;
}
int main(int argc, char *argv[])
{
ifstream in("autoput.in");
ofstream out("autoput.out");
int x, y, z, n, d, i;
int max = 0, sum = 0, l, r;
city gradovi[MAX];
in >> n >> d;
for (i = 0; i < n; i++){
city c;
in >> c.x >> c.y >> c.z;
gradovi[i] = c;
}
qsort(gradovi, n, sizeof(city), up);
l = 0; max = gradovi[0].z; sum = gradovi[0].z;
for (r = 1; r < n; r++){
while (gradovi[r].x-gradovi[l].x>2*d)
sum -= gradovi[l++].z;
sum += gradovi[r].z;
max >?= sum;
}
out << max << endl;
in.close();
out.close();
return EXIT_SUCCESS;
}
|
|
|