TAKMIČENJA IZ PROGRAMIRANJA


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.

mede.cpp    2,524 b      izvorni kod rešenja
mede.tests.rar    1,257,623 b      test primeri

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 ≤ aibi ≤ 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;   
}