36ος ΠΔΠ Γ' Φάση: Τυχεροί αριθμοί (luckyagain) - Λύση

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

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

Μας δίνεται μία λίστα από \(N\) αριθμούς και πρέπει να βρούμε πόσα ζευγάρια από αριθμούς μπορούμε να ενώσουμε ώστε να πάρουμε έναν τυχερό αριθμό.

Υπολογίζοντας τα ψηφία ενός αριθμού

Στις δύο παρακάτω λύσεις θα χρησιμοποιήσουμε τον εξής αλγόριθμο για την εύρεση των ψηφίων ενός αριθμού στην δεκαδική του αναπαράσταση. Ο αλγόριθμος βρίσκει διαδοχικά το τελευταίο ψηφίο του αριθμού (δηλαδή το υπόλοιπο του αριθμού με το \(10\)), αφαιρεί το τελευταίο ψηφίο (δηλαδή διαιρεί (ακέραια) τον αριθμό με το \(10\)) και συνεχίζει με τον υπόλοιπο αριθμό μέχρι να γίνει \(0\). Για παράδειγμα, αν ξεκινήσουμε με τον αριθμο \(x = 257\):

Στην πρώτη επανάληψη, λαμβάνουμε \(257 \bmod 10 = 7\) (το πρώτο ψηφίο) και έπειτα θέτουμε \(x = 257 / 10 = 25\).
Στην δεύτερη επανάληψη, λαμβάνουμε \(25 \bmod 10 = 5\) (το δεύτερο ψηφίο) και έπειτα θέτουμε \(x = 25 / 10 = 2\).
Στην τρίτη επανάληψη, λαμβάνουμε \(25 \bmod 10 = 2\) (το τρίτο ψηφίο) και έπειτα θέτουμε \(x = 2 / 10 = 0\).
Ο αριθμός έγινε μηδέν επομένως δεν έχει άλλα ψηφία.

Ο παρακάτω κώδικας υλοποιεί αυτόν τον αλγόριθμο και χρειάζεται χρόνο γραμμικό στο πλήθος των ψηφίων του αριθμού:¹

      while (temp > 0) {
         digits[i].push_back(temp % 10);
         temp /= 10;
      }

Εξαντλητική λύση

Χρησιμοποιώντας τον παραπάνω αλγόριθμο για την εύρεση των ψηφίων ενός αριθμού, μπορούμε να ελέγξουμε αν η ένωση δύο αριθμών είναι τυχερός αριθμός “ενώνοντας” τα ψηφία τους, αθροίζοντας τα πρώτα και τα τελευταία μισά, και τέλος ελέγχοντας αν το άθροισμά τους είναι ίσο. Ο αλγόριθμος που το κάνει αυτό είναι ο εξής (και είναι γραμμικός στο πλήθος των ψηφίων):

bool is_lucky(const std::vector<int>& digitsA, const std::vector<int>& digitsB) {
   int total_length = (digitsA.size() + digitsB.size());
   if (total_length % 2 == 1) return false; // Αν έχει μονό πλήθος ψηφίων, τότε δεν είναι τυχερός.
   
   int cur_sum[2]; 
   cur_sum[1] = 0; // Το άθροισμα των ψηφίων του πρώτου μισού.
   cur_sum[0] = 0; // Το άθροισμα των ψηφίων του δεύτερου μισού.
   
   int midpoint = total_length / 2;
   for (int i = 0; i < digitsA.size(); ++i) {
      cur_sum[i < midpoint] += digitsA[i];
   }
   for (int i = 0; i < digitsB.size(); ++i) {
      cur_sum[i + digitsA.size() < midpoint] += digitsB[i];
   }

   return cur_sum[0] == cur_sum[1];
}   

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

   // Μετράμε πόσα από τα δυνατά ζευγάρια φτιάχνουν έναν τυχερό αριθμό.
   ll total_count = 0;
   for (long i = 0; i < N; ++i) {
      for (long j = 0; j < N; ++j) {
         if (i == j) continue;
         total_count += is_lucky(digits[i], digits[j]);
      }
   }

Συνολικά ελέγχουμε \(Ν \cdot (N - 1)\) ζευγάρια και κάθε έλεγχος χρειάζεται το πολύ σταθερό αριθμό πράξεων (γιατί τα ψηφία κάθε αριθμού είναι το πολύ \(9\)). Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ

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

Ας υποθέσουμε ότι για κάποιον αριθμό \(x\) θέλουμε να μετρήσουμε όλους τους αριθμούς \(y\) για τους οποίους ισχύει ότι η ένωση τους \(xy\) είναι τυχερός αριθμός. Θέλουμε να το κάνουμε αυτό χωρίς να πρέπει να δοκιμάσουμε όλους τους δυνατούς αριθμούς \(y\).

Το ποια ψηφία του \(x\) συνεισφέρουν στο πρώτο και ποια στο τελευταίο μισό του αριθμού \(xy\), εξαρτάται από το που βρίσκεται το μέσο τους. Ας θεωρήσουμε ότι το μέσο τους βρίσκεται αμέσως μετά το \(i\)-οστό ψηφίο του \(x\), όπως στο ακόλουθο σχήμα (όπου \(\ell_x\) και \(\ell_y\) είναι το πλήθος των ψηφίων του \(x\) και \(y\) αντίστοιχα).

Τότε, ψάχνουμε για όλους τους αριθμούς \(y\) με \(\ell_y = 2i - \ell_x\) ψηφία (καθώς πρέπει \(i = (\ell_x - i) + \ell_y\) για να είναι \(i\) το μέσο) και άθροισμα ψηφίων \(s_y\) τέτοιο ώστε

\[x_1 + \ldots + x_i = x_{i+1} + \ldots + x_{\ell_x} + s_y \\ \Leftrightarrow \\ s_y = (x_1 + \ldots x_i) - (x_{i+1} + \ldots + x_{\ell_x}).\]

Για να βρούμε το πλήθος αυτών των αριθμών γρήγορα, προϋπολογίζουμε τον πίνακα \(\texttt{count}[\ell][s]\), που κρατάει το πλήθος των αριθμών με \(\ell\) ψηφία και άθροισμα ψηφίων \(s\). Έπειτα, για κάθε αριθμό \(x\) διατρέχουμε όλες τις θέσεις \(i\) των ψηφίων του και αθροίζουμε το πλήθος των αριθμών \(\texttt{count}[2i - \ell_x][(x_1 + \ldots + x_i) - (x_{i+1} + \ldots + x_{\ell_x})]\).

Μία αντίστοιχη συμμετρική συνθήκη προκύπτει όταν το \(x\) έρχεται μετά το \(y\) (και το μέσο βρίσκεται πάλι στο \(x\)).

Χρειάζεται προσοχή με τα ζεύγη αριθμών με το ίδιο πλήθος ψηφίων, καθώς αυτά θα τα μετρήσουμε δύο φορές, μία όταν ψάχνουμε για τυχερούς αριθμούς της μορφής \(x~\cdot\) και μία όταν ψάχνουμε για αριθμούς της μορφής \(\cdot~y\). Στον παρακάτω κώδικα η μεταβλητή \(\texttt{same\_digit\_count}\) μετράει πόσες τέτοιες περιπτώσεις υπάρχουν και αφαιρεί τις μισές από αυτές στο τέλος. Πρέπει επίσης να προσέξουμε να μην μετρήσουμε τα ζευγάρια της μορφής \(xx\).

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

#include <cstdio>
#include <vector>

typedef long long ll;

ll counts[10 /* πλήθος ψηφίων */][82 /* άθροισμα ψηφίων */]; // Πλήθος αριθμών

int main() {
   FILE *fi = fopen("luckyagain.in", "r");
   long N;
   fscanf(fi, "%ld", &N);
   
   std::vector<std::vector<int>> digits(N);
   std::vector<int> digit_sum(N, 0);
   
   for (int i = 0; i < N; ++i) {
      long temp;
      fscanf(fi, "%ld", &temp);
      
      // Βρίσκουμε τα ψηφία ενός αριθμού και το άθροισμά τους.
      while (temp > 0) {
         int cur_digit = temp % 10;
         digit_sum[i] += cur_digit;
         digits[i].push_back(cur_digit);
         temp /= 10;
      }
      
      // (Προ)-ϋπολογισμός του πίνακα counts.
      ++counts[digits[i].size()][digit_sum[i]];
   }
   fclose(fi);
   
   ll total_count = 0;
   // Οι αριθμοί με το ίδιο πλήθος ψηφίων θα μετρηθούν δύο φορές. Επομένως κρατάμε 
   // το πλήθος αυτών ώστε να το αφαιρέσουμε το μισό από το σύνολο.
   ll same_digit_count = 0;
   for (int j = 0; j < N; ++j) {
      const int sum_of_digits = digit_sum[j];
      const int len = digits[j].size();
      
      // Βρίσκουμε το πλήθος των ζευγαριών που έχουν τον j-οστό αριθμό
      // σαν πρώτο μέρος και μέσο η θέση (len - i).
      int suffix_sum = 0;
      for (int i = 0; 2 * i < len; ++i) {
         ll cur_count = counts[len - 2 * i][sum_of_digits - 2 * suffix_sum];
         total_count += cur_count;
         if (i == 0) { // Το μέσο είναι στο τέλος του αριθμού.
            same_digit_count += cur_count - 1; // -1, για να μην μετρήσουμε τον εαυτό του.
         }
         suffix_sum += digits[j][i];
      }
      
      // Βρίσκουμε το πλήθος των ζευγαριών που έχουν τον j-οστό αριθμό
      // σαν δεύτερο μέρος και μέσο η θέση i.
      int prefix_sum = 0;
      for (int i = 0; 2 * i < len; ++i) {
         ll cur_count = counts[len - 2 * i][sum_of_digits - 2 * prefix_sum];
         total_count += cur_count;
         if (i == 0) { // Το μέσο είναι στην αρχή του αριθμού.
            same_digit_count += cur_count - 1;
         }
         prefix_sum += digits[j][len - i - 1];
      }
      
      // Αφαιρούμε τον εαυτό του απο την μέτρηση.
      total_count -= 2;
   }
   total_count -= same_digit_count / 2;
   
   FILE *fo = fopen("luckyagain.out", "w");
   fprintf(fo, "%lld\n", total_count);
   fclose(fo);
   
   return 0;
}

Στην C++ υπάρχουν επίσης οι συναρτήσεις itoa και sprintf στην standard βιβλιοθήκη, που κάνουν αυτούς τους υπολογισμούς (δείτε εδώ και εδώ). ↩