37ος ΠΔΠ : Μαγικό καζάνι (cauldron) - Λύση

Επεξήγηση εκφώνησης

Μας δίνεται μια ποσότητα μαγικού νερού \(K\) και \(N\) βάζα μαγικού ζωμού με γνωστά μεγέθη (το βάζο \(i\) έχει μέγεθος \(w_i\)). Μπορούμε να επιλέξουμε κάποια από τα \(N\) βάζα (η συνολική ποσότητα τους δεν πρέπει να υπερβαίνει το \(K\)) για να τα ρίξουμε στο καζάνι. Κάθε βάζο ποσότητας \(w_i\) που πέφτει στο καζάνι, αφαιρεί \(w_i\) μαγικό νερό και παράγει \(w_i+c\) μαγική σάλτσα. Το \(c\) είναι μια σταθερή τιμή που αυξάνει (αν είναι θετική) ή μειώνει (αν είναι αρνητική) την ποσότητα μαγικού ζωμού που παράγει κάθε βάζο που πέφτει στο καζάνι.
Όσο μαγικό νερό αφήσουμε στο καζάνι, θα μετατραπεί σε ισόποση μαγική σάλτσα. Ζητείται να υπολογίσουμε τη μέγιστη ποσότητα μαγικής σάλτσα που μπορεί να παραχθεί.

Υποπρόβλημα 1 (\(N\le 20\))

Δοκιμάζουμε όλους τους δυνατούς συνδυασμούς από βάζα και βρίσκουμε την καλύτερη επιλογή. Δεν ξεχνάμε να δοκιμάσουμε και την περίπτωση να μην πάρουμε κανένα βάζο (οπότε θα παραχθεί ακριβώς \(K\) ποσότητα σάλτσας). Οι δυνατοί συνδυασμοί των \(N\) βάζων είναι \(2^N\), αφού για κάθε βάζο έχουμε \(2\) επιλογές: να το πάρουμε ή να μην το πάρουμε.

Ένας τρόπος να βρεθούν όλοι οι συνδυασμοί, είναι με τη χρήση αναδρομής:

void calc(long Krem,int i,ll csum=0){//Krem=μαγικό νερο στο καζάνι, csum=κέρδος από τα c
    if(i==N){
        ans = max(ans, K + csum);
        return;
    }
    calc(Krem,i+1,csum);//αν δεν πάρουμε το i
    if(Krem>=w[i])//έχουμε αρκετό μαγικό νερό;
        calc(Krem-w[i],i+1,csum+c);//αν πάρουμε το i
}

Ολόκληρος ο κώδικας εδώ.

Ένας διαφορετικός τρόπος είναι να απαριθμήσουμε με ένα βρόχο στη μεταβλητή \(s\) από το \(0\) (κανένα βάζο) έως και το \(2^N-1\) (όλα τα βάζα). Ο αριθμός \(2^N-1\) στο δυαδικό σύστημα απεικονίζεται με \(N\) άσους και σε κάθε επανάληψη ελέγχουμε αν το \(i\)-οστό bit είναι αναμμένο (\(1\)) οπότε θα χρησιμοποιήσουμε το αντίστοιχο βάζο, ή σβηστό (\(0\)) οπότε δεν θα το χρησιμοποιήσουμε.

        for(long s=0,m=(1L<<N);s<m;s++){
            long Krem = K;//πόσο μαγικό νερό παραμένει στο καζάνι
            ll test = 0;
            for(int i=0;i<N;i++){
                if((s&(1L<<i)) && Krem>=w[i]){
                    test += w[i] + c;
                    Krem -= w[i];
                }
            }
            test += Krem;
            ans = max(ans,test);
        }

Ολόκληρος ο κώδικας εδώ. Η λύση αυτή χρειάζεται \(\mathcal{O}(N \cdot 2^N)\) χρόνο, διότι για κάθε ένα συνδυασμό, ελέγχουμε τα \(N\) bits του.

Υποπρόβλημα 2 (\(c \le 0\))

Κάθε βάζο \(i\) προσφέρει ζωμό όσο ο όγκος του (\(w_i\)) προσαυξημένο, με τη σταθερά \(c\). Αν δεν χρησιμοποιήθεί κανένα βάζο, θα παραχθεί σάλτσα ποσότητας \(K\) χωρίς τις προσαυξήσεις της \(c\). Στο υποπρόβλημα αυτό που η σταθερά \(c\) μας αφαιρεί σάλτσα (αν είναι αρνητική) ή δεν μας προσαυξάνει τη σάλτσα (αν είναι μηδενική), δεν χρειάζεται να πάρουμε κανένα βάζο. Ο χρόνος που απαιτείται είναι \(\mathcal{O}(1)\) (σταθερός) καθώς δεν επηρεάζεται από το \(N\).

Υποπρόβλημα 3 (όλα τα βάζα είναι ίδια)

Όπως και στο προηγούμενο υποπρόβλημα, θα αποφασίσουμε από το \(c\) αν θα χρησιμοποιήσουμε βάζα ή όχι. Αν το \(c\) είναι θετικό, τότε θέλουμε όσα περισσότερα βάζα μπορούμε να χρησιμοποιήσουμε (ώστε να κερδίσουμε πολλά \(c\)). Ο χρόνος που απαιτείται σε αυτό το υποπρόβλημα, είναι \(\mathcal{O}(1)\), καθώς αρκεί να διαβάσουμε την ποσότητα μόνο ενός βάζου για να υπολογίσουμε την απάντηση.

        scanf("%ld",&w0);//διάβασε ποσότητα ζωμού ενός βάζου
        if(c>0){
            long jars = min(K/w0,N);
            ans += (ll)jars*c;
        }

Ολόκληρος ο κώδικας εδώ.

Πλήρης λύση

Αν το \(c\) είναι θετικό, θέλουμε όσα περισσότερα \(c\) μπορούμε να πάρουμε, οπότε θέλουμε να μεγιστοποιήσουμε τον αριθμό βάζων που χωράνε στο \(K\). Παρατηρήστε ότι μας συμφέρει να πάρουμε το μικρότερο βάζο που είναι διαθέσιμο, καθώς θα καταναλώσει τη μικρότερη ποσότητα μαγικού νερού, αφήνοντας το υπόλοιπο μαγικό νερό για τα υπόλοιπα βάζα. Ταξινομούμε τα βάζα με το \(w_i\), και χρησιμοποιούμε τα μικρότερα βάζα που η συνολική τους ποσότητα να μην ξεπεράσει το \(K\).

    if(c>0){
        sort(w.begin(),w.end());
        long Krem = K;//πόσο μαγικό νερό παραμένει στο καζάνι
        for(auto e:w){
            if(e<=Krem){
                ans += c;
                Krem -= e;
            } else break;
        }
    }
    printf("%lld\n",ans);

Ολόκληρος ο κώδικας εδώ. O συνολικός χρόνος της λύσης αυτής, είναι \(\mathcal{O}(N\cdot \log_2{N})\) (λόγω της ταξινόμησης).