38ος ΠΔΠ Γ' Φάση: Ψωνίζοντας με τον Τάκη (shopping) - Λύση

Μέρος 1ο

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

Μας δίνονται οι τιμές \(N\) προϊόντων \(V_1, \ldots , V_N\). Ο Τάκης έχει ένα αρχικό ποσό \(X\) και κάθε φορά ψάχνει το αντικείμενο με το μεγαλύτερο κόστος και το αγοράζει. Επαναλαμβάνει αυτή τη διαδικασία έως ότου δεν μπορεί να αγοράσει κάτι άλλο. Μας δίνονται \(Q\) αρχικά ποσά \(X_1, \ldots, X_Q\) και πρέπει για κάθε ένα από αυτά να βρούμε το ποσό που μένει στον Τάκη όταν τελειώσει τα ψώνια του.

Brute force

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

Ο παρακάτω κώδικας υλοποιεί αυτή την στρατηγική:

    ll x;
    scanf("%lld", &x);
    while (true) {
      ll mx = -1;
      for (long i = 0; i < N; ++i)
        if (V[i] <= x)
          mx = std::max(mx, V[i]);
      if (mx == -1) break;
      x -= mx;
    }
    printf("%lld\n", x);

Στην χειρότερη περίπτωση θα χρειαστεί να διατρέξουμε όλα τα προϊόντα \(X_i\) φορές επομένως ο αλγόριθμος χρειάζεται \(O(Q \cdot N \cdot X_i)\) χρόνο. Αυτό είναι αρκετό για να περάσει το πρώτο υποπρόβλημα. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Λύση για \(N = 1\)

Όταν υπάρχει ένα μόνο αντικείμενο, το πλήθος των φορών που θα το πάρει ο Τάκης είναι ίσο με το πηλίκο της διαίρεσης \(X / V\) και το ποσό που θα του περισέψει είναι ίσο με το υπόλοιπο \(X \% V\). Επομένως, μπορούμε να απαντήσουμε κάθε ερώτημα σε \(O(1)\) χρόνο.

  while (Q--) {
    ll x;
    scanf("%lld", &x);
    printf("%lld\n", x % v);
  }

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

Βέλτιστη λύση

Επεκτείνοντας την παρατήρηση από την προηγούμενη λύση, όταν βρούμε το μέγιστο στοιχείο \(V_j \leq X_i\), τότε θα το πάρουμε \(X_i / V_j\) φορές και το καινούργιο ποσό θα είναι \(X_i' = X_i \% V_j\). Επίσης για να βρούμε γρήγορα το στοιχείο \(V_j\) κρατάμε τον πίνακα \(V\) ταξινομημένο και κάνουμε δυαδική αναζήτηση.

  std::sort(V, V + N);
  
  while (Q--) {
    ll x;
    scanf("%lld", &x);
    while (V[0] <= x) {
      // Βρίσκει το πρώτο στοιχείο με V[i] >= x + 1, 
      // δηλαδή με V[i] > x, δηλαδή με V[i-1] <= x.
      auto it = std::lower_bound(V, V + N, x + 1);
      --it;
      x = x % *it;
    }
    printf("%lld\n", x);
  }

Σε κάθε βήμα ο αριθμός μικραίνει τουλάχιστον στο μισό, επομένως για κάθε αριθμό χρειαζόμαστε το πολύ \(O(\log X_i)\) βήματα. Κάθε δυαδική αναζήτηση χρειάζεται \(O(\log N)\) βήματα, επομένως η λύση χρειάζεται \(O(N \log N + Q \log N \log X_i)\) βήματα, και είναι αρκετό για να περάσει όλα τα υποπροβλήματα. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Μέρος 2ο

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

Μας δίνονται \(T\) ποσά \(X_1, \ldots X_T\) από τα οποία μπορεί να ξεκινήσει ο Τάκης και εμείς πρέπει να βρούμε τις τιμές κάποιων προϊόντων ώστε να πάρει το μέγιστο δυνατό πλήθος διαφορετικών προϊόντων.

Δύο βασικές παρατηρήσεις είναι οι εξής:

1. Δεν έχει νόημα να έχουμε προϊόντα που δεν θα πάρει ο Τάκης.
2. Δεν έχει νόημα να έχουμε προϊόντα που θα πάρει πάνω από μία φορά ο Τάκης. (Αν ένα προϊόν είναι να το πάρει \(3\) φορές ο Τάκης, τότε μπορούμε να το αντικαταστήσουμε με \(3v\)).

Λύση με δυναμικό προγραμματισμό

Έστω \(\texttt{dp}[i]\) το μέγιστο πλήθος κουπονιών που μπορεί να πάρει ο Τάκης με αρχικό ποσό \(i\). Τότε αν \(j\) είναι η μεγαλύτερη τιμή που πήρε, τότε μπορούμε να υποθέσουμε ότι \(2j < i\), διαφορετικά θα μπορούσε να πάρει το \(2j\) χωρίς να αλλάξει κάτι στο πλήθος των κουπωνιών. Επομένως,

Χρησιμοποιώντας αυτή την αναδρομική σχέση και κρατώντας για κάθε \(i\) το βέλτιστο \(j\), έχουμε την εξής υλοποίηση:

  par[0] = -1;
  for (long i = 1; i <= MAXX; ++i) {
    par[i] = -1;
    dp[i] = -2;
    for (long j = 1; j <= i; ++j) {
      if (2 * j <= i) continue;
      if (par[i] == -1 || dp[i - j] + 1 > dp[i]) {
        par[i] = i - j;
        dp[i] = dp[i - j] + 1;
      }
    }
  }

και οι απαντήσεις δίνονται ως εξής:

    ll x;
    scanf("%lld", &x);
    printf("%ld\n", dp[x]);
    while (par[x] != -1) {
      printf("%lld ", x - par[x]);
      x = par[x];
    }
    printf("\n");

Ο υπολογισμός των τιμών του \(dp[\cdot]\) χρειάζεται \(O(X_i^2)\) χρόνο. Ο Τάκης μπορεί να κερδίσει το πολύ \(\log_2 X_i\) κουπόνια, επομένως ο αλγόριθμος χρειάζεται \(O(X_i^2 + T \log X_i)\) χρόνο και είναι αρκετό για να περάσει το πρώτο υποπρόβλημα. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Άπληστη λύση

Μπορούμε να παρατηρήσουμε ότι μπορούμε να κερδίσουμε \(\lceil \log_2 x \rceil\) κουπόνια με την εξής άπληστη στρατηγική, που προσπαθεί να μας πάει σε έναν αριθμό που έχει μόνο δυνάμεις του δύο στην δυαδική του αναπαράσταση και έπειτα να αφαιρέσει όλες τις δυνάμεις του δύο την μία μετά την άλλη.

• (Κοιτώντας τα βήματα ανάποδα) Στο \(k\)-οστό βήμα:
  • Αν \(2^{k+1} \leq x\), αφαιρούμε \(2^k\)
  • Διαφορετικά, αφαιρούμε \(x\).

  std::vector<ll> ans;
  while (T--) {
    ll x;
    scanf("%lld", &x);
    long cur_pow = 1; 
    ans.clear();
    while (x) {
      if (2 * cur_pow >= x) ans.push_back(x);
      else ans.push_back(cur_pow);
      cur_pow *= 2;
      x -= ans.back();
    }
    printf("%d\n", ans.size());
    printf("%lld", ans[0]);
    for (int i = 1; i < ans.size(); ++i) 
      printf(" %lld", ans[i]);
    printf("\n");
  }

Ο λόγος που αυτή η στρατηγική είναι βέλτιση είναι ότι αν \(x_1\) είναι το τελευταίο στοιχείο που πήραμε, \(x_2\) είναι το προ-τελευταίο, κ.ο.κ. τότε

δηλαδή \(x_k \geq 2^k\). Επομένως,

δηλαδή \(k \leq \log_2 (x + 1) - 1 \leq \lceil \log_2 x \rceil\) (που ισχύει όλους τους φυσικούς αριθμούς \(x\)).

Κάθε απάντηση χρειάζεται \(O(\log X_i)\) χρόνο επομένως συνολικά ο αλγόριθμος χρειάζεται \(O(T \log X_i)\) χρόνο. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.