24ος ΠΔΠ Α' Φάση: Υπολογιστικά νέφη (function) - Λύση

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

Προφανώς, το πρόβλημα δεν είναι καλώς ορισμένο. Δεδομένων οποιοδήποτε ζευγών εισόδων και εξόδων υπάρχουν άπειρα προγράμματα που μπορούν να παραγάγουν αυτά. Παρ’ όλα αυτά, το πρόβλημα μας ζητάει να βρούμε το πρόγραμμα που παραγάγει αυτά τα ζεύγη με τον πιο “λογικό” τρόπο. Ο πιο λογικός τρόπος, είναι ότι για τις εισόδους \((N, M)\) πρέπει να παράξουμε ως έξοδο τους πρώτους αριθμούς στο διάστημα \((N, M)\) (για \(N\leq M\)) ή \((M, N)\) (για \(M<N\)).

Για τις παρακάτω λύσεις ορίζουμε \(L = M - N\).

Λύση σε \(\mathcal{O}(L^2)\)

Ένας αριθμός είναι πρώτος αν διαιρείται μόνο από τον εαυτό του και το \(1\). Άρα μπορούμε να διατρέξουμε κάθε αριθμό \(k\) στο \((N, M)\) και να ελέγξουμε αν υπάρχει κάποιος άλλος αριθμός στο \([2, k-1]\) που να διαιρεί τον \(k\). Αν δεν υπάρχει, τότε ο αριθμός είναι πρώτος. Αν υπάρχει, τότε δεν είναι.

Σημείωση: Στις περισσότερες γλώσσες προγραμματισμού ελέγχουμε αν το \(i\) διαιρεί το \(k\), με k % i == 0 (δηλαδή, ελέγχουμε αν το υπόλοιπο της διαίρεσης του \(k\) με το \(i\) είναι \(0\)).

#include <algorithm>
#include <stdio.h>

bool isPrime(long k) {
   if (k == 1 || k == 2) return false;
   for (long i = 2; i < k; ++i) {
      if (k % i == 0) return false;
   }
   return true;
}

int main() {
   long N, M;
   FILE *fi = fopen("function.in", "r");
   fscanf(fi, "%ld%ld\n", &N, &M);
   fclose(fi);
   
   if (N > M) std::swap(N, M);
   
   FILE *fo = fopen("function.out", "w");
   bool is_first = true;
   for (long k = N + 1; k < M; ++k) {
      if (isPrime(k)) {
         if (!is_first) fprintf(fo, " ");
         fprintf(fo, "%ld", k);
         is_first = false;
      }
   }
   if (!is_first) {
      fprintf(fo, "\n");
   }
   fclose(fo);
   return 0;
}

Για κάθε αριθμό στο \((N, M)\), υπάρχουν \(k=\mathcal{O}(L)\) αριθμοί να ελέγξουμε. Άρα, ο αλγόριθμος χρειάζεται \(\mathcal{O}(L^2)\) χρόνο και \(\mathcal{O}(1)\) μνήμη.

Λύση σε \(\mathcal{O}(L\sqrt{L})\)

Mπορούμε να επιταχύνουμε τον παραπάνω αλγόριθμο με την εξής παρατήρηση:

Παρατήρηση: Αν ένας αριθμός \(k\) δεν είναι πρώτος, τότε θα έχει κάποιον διαιρέτη που είναι μικρότερος ή ίσος του \(\sqrt{k}\).

Απόδειξη: Έστω ότι \(λ>\sqrt{k}\) διαιρεί τον \(k\), τότε \(k=λ\cdot μ\) για κάποιο φυσικό \(μ\). Αν είναι επίσης \(μ>\sqrt{k}\), τότε \(k=λ\cdot μ > \sqrt{k} \cdot \sqrt{k} = k \implies k > k\), άτοπο. Συνεπώς, \(μ\leq \sqrt{k}\), που ολοκληρώνει την απόδειξη.

Αυτή η παρατήρηση, μας επιτρέπει για κάθε αριθμό \(k\) να ελέγξουμε μόνο τους αριθμούς \([2, \sqrt{k}]\) ως πιθανούς διαιρέτες. Άρα ο αλγόριθμος χρειάζεται \(\mathcal{O}(L\sqrt{L})\) χρόνο και \(\mathcal{O}(1)\) μνήμη.

Σημειώνουμε ότι αντί να ελέγχουμε ότι \(i \le \sqrt{k}\), υψώνουμε και τα δύο μέλη στο τετράγωνο, οπότε κάνουμε τον πιο εύκολο έλεγχο \(i*i \le k\).

bool isPrime(long k) {
   if (k == 1 || k == 2) return false;
   for (long i = 2; i * i <= k; ++i) {
      if (k % i == 0) return false;
   }
   return true;
}

Λύση με κόσκινο του Ερατοσθένη

Το κόσκινο του Ερατοσθένη δίνει μία μέθοδο να βρούμε όλους τους πρώτους μικρότερους από \(M\) σε χρόνο \(\mathcal{O}(M\log{M})\).

Το κόσκινο του Ερατοσθένη δουλεύει διαγράφοντας πολλαπλάσια πρώτων. Όταν φτάνει στον αριθμό \(k\), αν δεν έχει διαγραφεί, είναι πρώτος, διαφορετικά δεν είναι. Αν είναι πρώτος τότε για κάθε \(i\) με \(k\cdot i \leq M\), διαγράφουμε το \(k\cdot i\).

Mπορούμε να υλοποίησουμε το κόσκινο, κρατώντας έναν πίνακα από boolean μεγέθους \(M\), όπου το \(k\)-οστό στοιχείο δείχνει αν ο αριθμός \(k\) έχει διαγραφεί ή όχι. Όταν τελειώσει η διαδικασία, γνωρίζουμε για κάθε αριθμό αν είναι πρώτος ή όχι.

#include <algorithm>
#include <stdio.h>

const size_t MAXM = 10000;

bool isNotPrime[MAXM];

int main() {
   long N, M;
   FILE *fi = fopen("function.in", "r");
   fscanf(fi, "%ld%ld\n", &N, &M);
   fclose(fi);
   
   if (N > M) std::swap(N, M);

   isNotPrime[0] = isNotPrime[1] = true;
   for (long k = 2; k < M; ++k) {
      if (isNotPrime[k]) continue; 
      for (long i = 2; i * k <= M; ++i) {
         isNotPrime[i * k] = true;
      }
   }
   isNotPrime[2] = true;
   
   FILE *fo = fopen("function.out", "w");
   bool is_first = true;
   for (long k = N + 1; k < M; ++k) {
      if (!isNotPrime[k]) {
         if (!is_first) fprintf(fo, " ");
         fprintf(fo, "%ld", k);
         is_first = false;
      }
   }
   if (!is_first) {
      fprintf(fo, "\n");
   }
   fclose(fo);
   return 0;
}

Η μνήμη που χρησιμοποιεί ο αλγόριθμος είναι ένας πίνακας μεγέθους \(\mathcal{O}(M)\). Αν και δεν είναι υποχρεωτικό για το διαγωνισμό, το παρακάτω επιχείρημα δείχνει ότι ο χρόνος του αλγορίθμου είναι λιγότερος από \(\mathcal{O}(M\log{M})\).

Σημείωση: Αν ο αριθμός \(k\) δεν είναι πρώτος, τότε ο αλγόριθμος κάνει \(\mathcal{O}(1)\) χρόνο. Αν είναι, τότε πρέπει να διαγράψει τα στοιχεία \(2k, 3k, \ldots , \lfloor M/k \rfloor k\) (που είναι \(\mathcal{O}(M/k)\) στο πλήθος). Αθροίζοντας πάνω από όλα τα \(k\), έχουμε

Mεγαλώσαμε το άθροισμα ώστε να μπορέσουμε να το οργανώσουμε καλύτερα ώστε να φράξουμε το ζητούμενο. Το τρικ είναι να οργανώσουμε τα στοιχεία \(1/2, 1/3\), \(1/4, 1/5, 1/6, 1/7\), κοκ για τις δυνάμεις του \(2\). Για κάθε ένα από αυτά τα σύνολα το πρώτο στοιχείο είναι μεγαλύτερο από όλα τα άλλα (μεγαλύτερος παρονομαστής και ίδιος αριθμητής, σημαίνει μικρότερο κλάσμα). Άρα,

Υπάρχουν και πιο σφιχτά άνω φράγματα για τον χρόνο του αλγορίθμου.

Λύση με προϋπολογισμό

Αφού το \(M = 10.000\) είναι σχετικά μικρό, μπορούμε να προϋπολογίσουμε όλους τους πρώτους αριθμούς μικρότερους από \(M\) (χρησιμοποιώντας οποιανδήποτε από τις παραπάνω μεθόδους) και ανάλογα με την είσοδο να τυπώνουμε αυτούς που πρέπει σε \(\mathcal{O}(M)\) χρόνο και μνήμη (δείτε τον κώδικα εδώ).