|
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: Meda
|
Kao i sve male devojčice, Katarina obožava plišane mede. Zato je na vreme počela da se
priprema za Dan plišanih meda koji se održava u njenom gradiću. Na taj dan u svakoj
prodavnici igračaka svaki posetilac dobija na poklon po jednog plišanog medu.
Postoji n vrsta plišanih meda. Katarina je obilazila prodavnice i zaključila sledeće:
Neka su prodavnice numerisane brojevima od 1 do m. Za i-tu vrstu meda postoje
brojevi ai i bi koji govore da se taj meda prodaje u
prodavnicama numerisanim brojevima iz intervala [ai, bi].
Pre ili kasnije, Katarina će želeti da ima po jednog medu od svake vrste. Zato ona želi
da suma cena meda koje ne dobije tokom Dana plišanih meda bude što manja. Vaš zadatak
je da odredite minimalnu vrednost te sume. Pretpostavlja se da Katarina svaku prodavnicu
može posetiti najviše jedanput i da u prodavnici može izabrati bilo kog od meda koji se
u njoj prodaju.
Ulaz.
(Ulazni podaci se učitavaju iz datoteke mede.in.) U prvom redu ulazne datoteke
nalazi se broj n (n ≤ 20.000), ukupan broj vrsta plišanih meda.
Zatim se u narednih n redova nalaze po tri broja - u i-tom redu brojevi
ai, bi i ci
(1 ≤ ai ≤ bi ≤ 2.000, ci ≤ 10.000.000)
- ai i bi su granice intervala brojeva prodavnica u kojima se i-ta
vrsta meda prodaje, a ci je cena te vrste. Sve cene meda su različite.
Izlaz.
(Izlazni podaci se ispisuju u datoteku mede.out.) U izlaznoj datoteci treba da se
nalazi samo jedan broj - minimalna moguća suma cena meda koje Katarina ne dobije tokom
Dana plišanih meda.
Primer 1.
mede.in
|
|
mede.out
|
6
1 4 1
3 4 2
1 2 3
2 2 4
1 1 5
1 1 6
|
|
8
|
Objašnjenje.
Prvi meda se može pronaći u prodavnicama 1, 2, 3 i 4, i njegova cena je 1.
Drugi meda se može pronaći u prodavnicama 3 i 4, i njegova cena je 2, itd. Jedno od rešenja
je da u prodavnici 1 dobije medu 6, u prodavnici 2 medu 4, u prodavnici 3 medu 1 i u
prodavnici 4 medu 2. Tada joj preostaju mede 3 i 5, njihov zbir cena je 8.
Primer 2.
mede.in
|
|
mede.out
|
2
3 10 15
15 20 25
|
|
0
|
Objašnjenje.
Katarina može dobiti obe vrste meda, pa kasnije neće morati da kupi nijednog
medu.
|
|
fajl: mede.cpp
|
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxN = 20000, maxP = 2001;
struct meda { int start, end, cena; };
int n;
long long minCena;
meda mede[maxN];
int kupili[maxP], pom[maxP];
int komparatorPoCeni(const void *a, const void *b) {
meda *m1 = (meda*)a;
meda *m2 = (meda*)b;
return (int)(m2 -> cena - m1 -> cena);
}
int main() {
freopen("mede.in", "r", stdin);
freopen("mede.out", "w", stdout);
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d%d", &(mede[i].start), &(mede[i].end), &(mede[i].cena));
// sortiramo mede po ceni, od najskupljeg do najjeftinijeg
qsort(mede, n, sizeof(meda), komparatorPoCeni);
// na pocetku su nam sve prodavnice slobodne
for (int i = 0; i < maxP; i++)
kupili[i] = -1;
minCena = 0;
for (int i = 0; i < n; i++) {
// pokusavamo da dobijemo i-tog medu
int tekMeda = i;
int tekP = mede[i].start;
// prekidamo ako smo naisli na praznu prodavnicu ili ako nemamo vise prodavnica u kojima se
// tekuci meda prodaje
while ((tekMeda >= 0) && (tekP <= mede[tekMeda].end))
if (kupili[tekP] == -1) {
// ukoliko imamo slobodnu prodavnicu dodelicemo medu njoj i zavrsiti
pom[tekP] = tekMeda;
tekMeda = -1;
} else {
if (mede[tekMeda].end < mede[kupili[tekP]].end) {
// ako se meda kupljen u prodavnici koju trenutno posmatramo prodaje u vise prodavnica
// nego meda kojeg pokusavamo da dodamo, onda cemo njega uzeti kao tekuceg medu, a naseg
// medu kupiti u ovoj prodavnici
pom[tekP] = tekMeda;
tekMeda = kupili[tekP];
} else pom[tekP] = kupili[tekP];
tekP++; // prelazimo na sledecu prodavnicu
}
if (tekMeda < 0)
// ako smo imali slobodnu prodavnicu za medu, treba samo promene da sacuvamo
for (int j = mede[i].start; j <= tekP; j++)
kupili[j] = pom[j];
else
// nismo uspeli da dodamo i-tog medu, treba da povecamo cenu meda koje ne mozemo dobiti
minCena += mede[i].cena;
// stanje prodavnica ostaje kakvo je bilo
}
printf("%lld\n", minCena);
return 0;
}
|
|
|