Αρχική > 35ος ΠΔΠ > coupon (εκφώνηση)

35ος ΠΔΠ Α' Φάση: Ηλεκτρονικές κάρτες αγορών (coupon) - Λύση

Συγγραφέας: Βαγγέλης Κηπουρίδης

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

Η συγκεκριμένη εκφώνηση είναι αρκετά ιδιαίτερη. Αν δεν την καταλάβετε στην παρακάτω μορφή, προτείνουμε να διαβάσετε την επίσημη εκφώνηση.

Εν συντομία, μας δίνεται μια λίστα με \(N\) αριθμούς \(C_1, \ldots, C_N\), ένας δεκαδικός αριθμός \(A\) μεταξύ \(0\) και \(1\), κι ένας αριθμός \(B\). Για κάθε ακέραιο \(X\) ορίζουμε την παρακάτω διαδικασία (σε ψευδοκώδικα):

integer TotalMoney(integer X) {
  integer s=0;
  for(integer i=1; i<=N; ++i) {
    if (X<10) X=0;
    s = s + X*C[i];
    X = A*X;    
  }
  return s;
}

Ο στόχος είναι να βρούμε το μέγιστο \(X\) έτσι ώστε \(\texttt{TotalMoney}(X) \le B\).

Λύση 1Α - Γραμμική αναζήτηση από κάτω

Είναι εύκολο να δούμε ότι όταν αυξάνουμε το \(X\), αυξάνεται και η \(\texttt{TotalMoney}(X)\) (για να είμαστε κάπως πιο ακριβείς: δεν μειώνεται η \(\texttt{TotalMoney}(X)\)).

Μία πολύ απλή λύση είναι να δοκιμάσουμε όλα τα πιθανά \(X\). Σταματάμε την πρώτη φορά που θα συναντήσουμε ένα \(X\) για το οποίο \(\texttt{TotalMoney}(X)>B\), και επιστρέφουμε το ακριβώς προηγούμενο \(X\). Ο λόγος που σταματάμε και δεν ψάχνουμε για άλλα \(X\) είναι ακριβώς το γεγονός ότι η \(\texttt{TotalMoney}(X)\) δεν πρόκειται να μικρύνει όσο αυξάνουμε το \(X\). Άρα για κάθε μεγαλύτερο \(X\), η \(\texttt{TotalMoney}(X)\) θα ήταν μεγαλύτερη από \(B\), κι άρα δεν μας απασχολεί.

Ενδεικτικά δίνουμε τον παρακάτω κώδικα για το πρόβλημα:

#include <cstdio>

typedef unsigned long long ull;

const size_t MAXN = 1000;

long N, C[MAXN+1];
double A;
ull B;
FILE *fo;

ull TotalMoney(ull X, bool printIt) {
  ull s=0;
  for(long i=1; i<=N; ++i) {
    if (X<10) X=0;
    s+=X*C[i]; //the product doesn't fit in type 'long' - that's why we declare X as type 'ull'
    if(printIt) fprintf(fo, "%llu\n", X);
    X = (long)(A*X);    
  }
  return s;
}

int main() {
   long X;  
   FILE *fi = fopen("coupon.in", "r");
   fscanf(fi, "%ld %lf %llu", &N, &A, &B);
   for (long i = 1; i <= N; ++i) {
      fscanf(fi, "%ld", &C[i]);
   }
   fclose(fi);

   //the following loop does not have a main-body, it only searches for X - that's why it ends with ';'   
   for(X=1; TotalMoney(X,false)<=B; ++X);
   --X;
     
   fo = fopen("coupon.out", "w");
   fprintf(fo, "%llu\n", TotalMoney(X,false));
   TotalMoney(X,true);
   fclose(fo);   
   return 0;
}

Προσέξτε την εξής γραμμή:

s += X*C[i];

Παρότι η μεταβλητές \(X\) και \(C[i]\) χωράνε σε απλό integer, το γινόμενό τους μπορεί να είναι πολύ μεγάλο και να μη χωράει. Έτσι προτιμήσαμε να δηλώσουμε τη \(X\) ως unsigned long long, ώστε η \(\texttt{C++}\) αυτόματα να καταλαβαίνει ότι το γινόμενο πρέπει κι αυτό να μπει σε unsigned long long. Εναλλακτικά θα μπορούσαμε να κάνουμε:

s += (unsigned long long)X*C[i];

Να θυμάστε πάντα όταν το πρόγραμμά σας κάνει πολλαπλασιασμούς, ότι κινδυνεύετε οι αριθμοί να μη χωράνε σε ακέραιες μεταβλητές. Η λύση είναι να χρησιμοποιήσετε long long.

Η λύση αυτή μπορεί να είναι πολύ αργή επειδή χρειάζεται να ελέγξει πάρα πολλά διαφορετικά \(X\). Στην χειρότερη περίπτωση θα ελέγξει \(B\) διαφορετικές τιμές για το \(X\), και ο κάθε έλεγχος τρέχει την συνάρτηση \(\texttt{TotalMoney}\) η οποία απαιτεί \(\mathcal{O}(N)\) χρόνο. Συνεπώς η πολυπλοκότητα είναι \(\mathcal{O}(N\cdot B)\).

Παρόλα αυτά, επειδή είναι πρόβλημα της Α’ Φάσης του διαγωνισμού, μπορείτε να περιμένετε να πάρει τους περισσότερους (ή ίσως και όλους) τους βαθμούς.

Λύση 1Β - Γραμμική αναζήτηση από πάνω

Ακριβώς με την ίδια λογική με την προηγούμενη λύση, μπορούμε να δοκιμάσουμε πάλι να ψάχνουμε ένα-ένα όλα τα \(X\), αλλά αυτή τη φορά να ξεκινήσουμε από μία πολύ μεγάλη τιμή, αντί για μία μικρή τιμή. Έτσι θα σταματούσαμε όταν βρίσκαμε το πρώτο \(X\) για το οποίο \(\texttt{TotalMoney}(X)\le B\). Οι αλλαγές στον κώδικα θα ήταν πολύ λίγες. Αντί για:

   for(X=1; TotalMoney(X,false)<=B; ++X);
   --X;

θα είχαμε:

   for(X=B/C[1]+10; TotalMoney(X,false)>B; --X);

Εδώ μπορείτε να βρείτε και ολόκληρο τον κώδικα.

Μερικές επεξηγήσεις:

  • Η μεγάλη τιμή απ’ την ξεκινάμε είναι η \(B/C[1]\). Ο λόγος είναι ότι αν το \(X\) ήταν μεγαλύτερο, τότε η διαδικασία \(\texttt{TotalMoney}\) θα ξεκινούσε πολλαπλασιάζοντας το \(X\) με το \(C[1]\), κι άρα θα έδινε κάτι μεγαλύτερο του \(B\). Αυτό προφανώς δε μας χρειάζεται. Η μόνη εξαίρεση είναι αν το \(B/C[1]\) είναι μικρότερο από 10, διότι η \(\texttt{TotalMoney}\) αγνοεί τόσο μικρές τιμές. Προσθέτοντας 10 γλιτώνουμε από αυτές τις οριακές περιπτώσεις.
  • Αυτή τη φορά δε χρειάζεται να τυπώσουμε το \(X-1\), ακριβώς επειδή σταματάμε μόλις βρούμε το \(X\) για το οποίο \(\texttt{TotalMoney}(X)\le B\), που είναι το ζητούμενο. Θυμίζουμε ότι προηγουμένως σταματούσαμε όταν βρίσκαμε \(X\) για το οποίο \(\texttt{TotalMoney}(X)>B\), το οποίο είναι κατά ένα μεγαλύτερο από το ζητούμενο.

Όπως και προηγουμένως, η πολυπλοκότητα είναι \(\mathcal{O}(N\cdot B)\). Παρόλα αυτά, επειδή είναι πρόβλημα της Α’ Φάσης του διαγωνισμού, μπορείτε να περιμένετε να πάρει τους περισσότερους (ή ίσως και όλους) τους βαθμούς.

Λύση 2 - Γραμμική αναζήτηση κι από πάνω κι από κάτω

Προσέξτε ότι αν η πραγματική απάντηση είναι πολύ κοντά στο 0, τότε θα την βρει γρήγορα η λύση 1A, αλλά όχι η 1B. Απ’ την άλλη πλευρά, αν η λύση είναι πολύ μεγάλη (κοντά στο \(B/C[1]\)) τότε θα την βρει γρήγορα η λύση 1B αλλά όχι η 1A.

Υπάρχει όμως ένας τρόπος να κρατήσουμε τα καλά στοιχεία και των 2 λύσεων. Αρκεί να ψάχνουμε το \(X\) με την εξής σειρά:

\[1, B/C[1], 2, B/C[1]-1, 3, B/C[1]-2, 4, B/C[1]-3, \ldots\]

Μπορείτε να φανταστείτε γιατί αυτή η λύση θα κάνει χρόνο αντίστοιχο με την καλύτερη μεταξύ των 1Α και 1Β; Για την ακρίβεια θα κάνει διπλάσιο χρόνο, αλλά αυτό για τους υπολογιστές δεν είναι σημαντικό πρόβλημα.

Δεν δίνουμε κώδικα για αυτή τη λύση, διότι στην χειρότερη περίπτωση παίρνει ίδιο χρόνο με τις προηγούμενες, ενώ ο κώδικάς της είναι πιο δύσκολος. Την αναφέρουμε μόνο για την ενδιαφέρουσα ιδιότητα να συνδυάζει τα θετικά των προηγούμενων δύο λύσεων.

Λύση 3 - Δυαδική αναζήτηση

Αν το καλοσκεφτείτε, πραγματικά το μόνο που κάνουμε στις προηγούμενες λύσεις είναι μία γραμμική αναζήτηση για την ιδανική τιμή \(X\), μέσω αυτής της γραμμής κώδικα:

   for(X=1; TotalMoney(X,false)<=B; ++X);
   --X;

Όμως η συνάρτηση \(\texttt{TotalMoney}\), όπως παρατηρήσουμε και προηγουμένως, είναι μονότονη (αύξουσα). Με άλλα λόγια, για οποιοδήποτε \(X\) ισχύει ότι \(\texttt{TotalMoney}(X) \le \texttt{TotalMoney}(X+1)\). Επομένως μπορούμε να κάνουμε δυαδική αναζήτηση. Αν δεν έχετε ξανακούσει τι είναι η δυαδική αναζήτηση, μπορείτε να δείτε εδώ.

Αντικαθιστούμε λοιπόν τις παραπάνω γραμμές κώδικα με:

   long lo=0, mid, hi=B/C[1]+10;
   while (lo<hi) {
     mid = (lo+hi+1)/2;
     if(TotalMoney(mid,false)<=B) lo=mid;
     else hi=mid-1;
   }
   X=lo;

Εδώ μπορείτε να βρείτε και ολόκληρο τον κώδικα.

Το μόνο αξιοσημείωτο στον παραπάνω κώδικα είναι ότι αντί για το συνηθισμένο:

mid = (lo+hi)/2

κάνουμε:

mid = (lo+hi+1)/2

Ο πρώτος κώδικας θα στρογγυλοποιούσε προς τα κάτω, σε περίπτωση που το αποτέλεσμα της διαίρεσης είναι δεκαδικό, επειδή έτσι λειτουργεί η \(\texttt{C++}\). Ο δεύτερος (τον οποίο χρησιμοποιούμε) προσθέτει +1/2, το οποίο στη συγκεκριμένη περίπτωση ισοδυναμεί με στρογγυλοποίηση προς τα πάνω.

Ένας απλός τρόπος να θυμάστε ποιον χρησιμοποιούμε ανά περίπτωση είναι ο εξής: Αν κάνουμε lo = mid + 1 και hi = mid, τότε θα έπρεπε να έχει χρησιμοποιηθεί ο πρώτος κώδικας. Αν κάνουμε lo = mid και hi = mid - 1, τότε θα έπρεπε να έχει χρησιμοποιηθεί ο δεύτερος κώδικας.

Αν αναρωτιέστε από πού προκύπτει αυτό το περίεργο, προσπαθείστε να φανταστείτε τι συμβαίνει όταν έχουν απομείνει μόνο 2 στοιχεία. Θα δείτε ότι ο ένας κώδικας δίνει ατέρμονα βρόγχο, ενώ ο άλλος τερματίζει κανονικά.

Η πολυπλοκότητα τώρα είναι \(\mathcal{O}(N\cdot \log{B})\) αφού η δυαδική αναζήτηση χρειάζεται μόνο \(\mathcal{O}(\log{B})\) δοκιμές αντί για \(B\). Έτσι αυτή η λύση θα έπαιρνε όλους τους βαθμούς ακόμα κι αν τα αρχεία ελέγχου ήταν επίτηδες πολύ ζόρικα.