31ος ΠΔΠ Α' Φάση: Υποθαλάσσιοι υδρογονάνθρακες (hydrocarbons) - Λύση

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

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

Μας δίνονται \(N\) τριάδες \((a,b,c)\), και καλούμαστε να υπολογίσουμε για την κάθε τριάδα αν η αποδοτικότητά της είναι θετική. Κατόπιν ταξινομούμε τις θετικές αποδοτικότητες με φθίνουσα σειρά (σε περίπτωση που δύο τριάδες έχουν ίση αποδοτικότητα, τυπώνουμε πρώτα αυτή που εμφανίζεται νωρίτερα στο αρχείο εισόδου). Ως αποδοτικότητα ορίζεται η τιμή: \(a-\frac{ab}{3000}-\frac{ac}{40}\)

Π.χ. για \((a,b,c)=(5,6,8)\) έχουμε αποδοτικότητα \(5-\frac{5 \cdot 6}{3000}-\frac{5 \cdot 8}{40} = 3.99\)

Παρακάτω θα δούμε:

Μία λύση που φαίνεται απόλυτα λογική, αλλά βγάζει σφάλματα.
Επεξήγηση σφαλμάτων (περιορισμένη ακρίβεια) και αντιμετώπιση.
Μια καλύτερη αντιμετώπιση!
Μια σύντομη αναφορά στην αναπαράσταση δεκαδικών αριθμών.

Βασική λύση (όμως λανθασμένη).

Η λύση του προβλήματος θα ήταν πολύ απλή: Διαβάζουμε την είσοδο και υπολογίζουμε την αποδοτικότητα κάθε τριάδας. Δημιουργούμε ένα πίνακα που εισάγουμε τις τριάδες που έχουν θετική αποδοτικότητα (αποθηκεύουμε μαζί και τη θέση που είχαν στην είσοδο, καθώς θα χρειαστεί για την ταξινόμηση). Κατόπιν ταξινομούμε αυτές τις τιμές με τη συνάρτηση sort.

Παρατήρηση 1: Ο έλεγχος για το αν μία αποδοτικότητα είναι θετική μπορεί να είναι και απλά:

if(1.0-b/3000.0-c/40.0 > 0.0)

καθώς το \(a\) μπορεί να βγει κοινός παράγοντας. Όσες λύσεις προτίμησαν αυτή την εκδοχή είναι εξίσου σωστές. Βεβαίως και δεν είναι λάθος να γίνει ο κλασικός έλεγχος:

if(a-a*b/3000.0-a*c/40.0 > 0.0)

Παρατήρηση 2: Εφόσον υπάρχουν διαιρέσεις, χρησιμοποιούμε double αριθμούς, όχι integers! Κι αφού χρησιμοποιούμε doubles, καλό είναι όπου υπάρχουν σταθερές (πχ \(40\)) να τις γράφουμε σε δεκαδική μορφή (πχ \(40.0\)). Γιατί; Αν τυπώσουμε την τιμή \(5/2\) θα πάρουμε απάντηση \(2\) αντί για \(2.5\), καθώς ο υπολογιστής φαντάζεται ότι δε μας ενδιαφέρει το δεκαδικό κομμάτι. Βεβαίως αν τυπώσουμε \(5.0/2.0\) θα πάρουμε πράγματι \(2.5\)!

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

#include <bits/stdc++.h>
using namespace std;

struct ApodosiThesi {
   double apodosi;
   long thesi;
} Thetika[100001];

bool compare (ApodosiThesi ena, ApodosiThesi dio) {
   if (ena.apodosi != dio.apodosi) 
       return ena.apodosi > dio.apodosi;
   return ena.thesi < dio.thesi;
}

int main() {
   double a, b, c, apodosi;
   long N, posaThetika = 0;
   freopen("hydrocarbons.in","r",stdin);
   freopen("hydrocarbons.out","w",stdout);
   scanf("%ld", &N);
  
   for(long i=1; i<=N; ++i) {
      scanf("%lf %lf %lf", &a, &b, &c);
      apodosi = a-a*b/3000.0-a*c/40.0;
      if (apodosi > 0) {
         ++posaThetika;
         Thetika[posaThetika].apodosi = apodosi;
         Thetika[posaThetika].thesi = i;
      }
   }
   sort(Thetika+1, Thetika+posaThetika+1, compare);
   printf("%ld\n", posaThetika);
   for(long i=1; i<=posaThetika; ++i) {
      printf("%ld", Thetika[i].thesi);
      if(i<posaThetika) printf(" ");
      else printf("\n");
   }
   return 0;
}

Περιορισμένη ακρίβεια

Τι το λάθος έχει ο παραπάνω κώδικας; Δυστυχώς όταν δουλεύουμε με double αριθμούς (λόγω της διαίρεσης), υπάρχουν σφάλματα ακρίβειας. Αυτό πολύ απλά σημαίνει ότι δε μπορούμε να αποθηκεύσουμε οσοδήποτε μεγάλους αριθμούς στον υπολογιστή. Απλοποιημένα, σκεφτείτε να προσπαθήσουμε να αποθηκεύσουμε σε ένα τετράδιο, σε δεκαδική μορφή, το \(\frac{1}{3}\). Πόσο πολύ θα αποθηκεύσουμε; \(0.3\); Μήπως \(0.33\); Μήπως \(0.333\); Όσο πολλά ψηφία και να γράψουμε, πάντα θα υπάρχει κάποιο σφάλμα.

Και τι προβλήματα δημιουργεί αυτό; Πολύ μικρά! Επειδή ο υπολογιστής μπορεί να αποθηκεύσει πολλά ψηφία, τα σφάλματα γίνονται απειροελάχιστα (πολύ μικρότερα από 0.000001). Παρότι μικρά, βέβαια, είναι υπαρκτά. Έτσι, ενώ δύο αριθμοί μπορεί στην πραγματικότητα να είναι ίσοι, στον υπολογιστή ίσως απέχουν ελάχιστα. Για το λόγο αυτό, όταν ελέγχουμε για ισότητα σε double αριθμούς, αντί να κάνουμε:

bool Equal(double a, double b) {
    return a==b;
}

προτιμούμε το:

bool Equal(double a, double b) {
    return fabs(a-b) < 0.000001;
}

Η συνάρτηση fabs είναι απλώς η απόλυτη τιμή για double αριθμούς. Στην ουσία, αντί να ελέγξουμε για ισότητα, κοιτάμε αν η απόστασή των αριθμών είναι δραματικά μικρή (το πολύ 0.000001), λόγω των σφαλμάτων.

Έτσι, στον παραπάνω κώδικα αντί για:

if (ena.apodosi != dio.apodosi)

θα είχαμε:

if (fabs(ena.apodosi - dio.apodosi) > 0.000001)

Αντίστοιχα, δεν αρκεί να ελέγξουμε:

if (apodosi > 0)

αλλά πρέπει να βεβαιώσουμε και ότι δεν είναι ακριβώς 0, κι απλά λόγω σφαλμάτων φαίνεται μεγαλύτερο. Δηλαδή πρέπει να ελέγξουμε:

if(apodosi > 0 && fabs(apodosi) > 0.000001)

Σημείωση: το \(0.000001\) δεν εξαρτάται από το πρόβλημα, χρησιμοποιούμε πάντα αυτή την τιμή κι έχουμε το κεφάλι μας ήσυχο!

Για να μη μπερδευόμαστε…

Εκτός από την παραπάνω λύση, υπάρχει κι άλλη μία πιο ενδιαφέρουσα: όλα τα προβλήματα προέκυψαν από το γεγονός ότι δουλέψαμε με double. Πράγματι, όταν δουλεύουμε με ακεραίους μπορούμε να ελέγξουμε κλασικά για ισότητα. Πώς αντιμετωπίζουμε λοιπόν τη διαίρεση που ζητάει το πρόβλημα; Πολύ απλά, αντί να υπολογίσουμε την αποδοτικότητα:

\[a-\frac{ab}{3000}-\frac{ac}{40}\]

θα υπολογίζουμε την αποδοτικότητα πολλαπλασιασμένη με \(3000\):

\[3000a-ab-75ac\]

Παρατηρούμε ότι όποτε η αποδοτικότητα είναι θετική, τότε και η αποδοτικότητα_επί_3000 είναι θετική. Επίσης είναι ισοδύναμο να ταξινομήσουμε με βάση την αποδοτικότητα, και να ταξινομήσουμε με βάση την αποδοτικότητα_επί_3000.

Όμως η νέα αποδοτικότητα έχει μόνο ακέραιες τιμές, καθώς δεν υπάρχουν καθόλου παρονομαστές! Η μόνη προσοχή που χρειαζόμαστε είναι ότι η τιμή \(3000a\) μπορεί να είναι μεγαλύτερη από τη χωρητικότητα ενός integer, κι έτσι προτιμάμε long long integers.

Ο κώδικας είναι ο παρακάτω:

#include <bits/stdc++.h>

using namespace std;

struct ApodosiThesi {
   long long apodosi;
   long thesi;
} Thetika[100001];

bool compare (ApodosiThesi ena, ApodosiThesi dio) {
   if (ena.apodosi != dio.apodosi)
      return ena.apodosi > dio.apodosi;
   return ena.thesi < dio.thesi;
}

int main() {
   long long a, b, c, apodosi;
   long N, posaThetika = 0;
   freopen("hydrocarbons.in","r",stdin);
   freopen("hydrocarbons.out","w",stdout);
   scanf("%ld", &N);
  
   for(long i=1; i<=N; ++i) {
      scanf("%lld %lld %lld", &a, &b, &c);
      apodosi = 3000*a-a*b-75*a*c;
      if (apodosi > 0) {
         ++posaThetika;
         Thetika[posaThetika].apodosi = apodosi;
         Thetika[posaThetika].thesi = i;
      }
   }

   sort(Thetika+1, Thetika+posaThetika+1, compare);
   printf("%ld\n", posaThetika);
   for(long i=1; i<=posaThetika; ++i) {
      printf("%ld", Thetika[i].thesi);
      if(i<posaThetika) printf(" ");
      else  printf("\n");
   }
   return 0;
}

Και οι δύο λύσεις είναι εξίσου σωστές, μη φοβηθείτε τους double αφού πλέον γνωρίζετε να τους συγκρίνετε για ισότητα!

Διαλέγετε όποια από τις δύο προτιμάτε!!!

Μια σύντομη σημείωση για τους δεκαδικούς

Οι ακέραιοι αριθμοί αναπαρίστανται στον υπολογιστή στο δυαδικό σύστημα χρησιμοποιώντας συνολικά 32 bit (συνήθως) τα οποία αντιστοιχούν στα δυαδικά ψηφία. Για παράδειγμα, ο αριθμός \(42\) θα αποθηκευτεί ως:

\[00000000000000000000000000101010 = 2^1+ 2^3 + 2^5\]

Η δεξιότερη θέση αντιστοιχεί στο \(2^0\), η επόμενη στο \(2^1\), κλπ.

Για να αναπαραστήσουμε αρνητικούς ακεραίους, χρησιμοποιούμε το αριστερότερο ψηφίο ως το πρόσημο (\(0\)=θετικό, \(1\)=αρνητικό). Στην πραγματικότητα κάνουμε και κάτι ακόμα (αντιστρέφουμε όλα τα άλλα ψηφία και κατόπιν προσθέτουμε \(1\)!), αλλά αυτό δε θα μας απασχολήσει καθόλου. Ενδεικτικά αναφέρουμε ότι το \(-42\), θα αποθηκευτεί ως:

\[11111111111111111111111111010110\]

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

Πώς θα μπορούσαμε να αναπαραστήσουμε τους πραγματικούς αριθμούς; Αρχικά πρέπει να συμβιβαστούμε με το γεγονός ότι για να έχουμε μία σύντομη αναπαράσταση (πχ \(32\) bit), θα πρέπει υποχρεωτικά να έχουμε σφάλματα στην ακρίβεια, καθώς η αναπαράσταση κάποιων αριθμών (πχ του \(π\)) θα απαιτούσε άπειρα bit! Μία λύση θα ήταν τα πρώτα \(16\) bit να αντιστοιχούν στο ακέραιο μέρος και τα υπόλοιπα στο δεκαδικό. Αυτού του είδους η λύση λέγεται fixed point arithmetic, καθώς το πλήθος των δεκαδικών ψηφίων μένει σταθερό. Η λύση αυτή, παρότι πολύ ακριβής, δε μας δίνει τη δυνατότητα να αναπαραστήσουμε μεγάλους αριθμούς (μόνο \(16\) bit είναι ελάχιστα για το ακέραιο μέρος).

Η πιο συνηθισμένη λύση είναι παρόμοια με την επιστημονική γραφή (π.χ. \(π\simeq 31415\cdot 10^{-4}\)), όπου ο αριθμός γράφεται ως \(x\cdot 2^{y}\) και οι \(x, y\) είναι ακέραιοι που αναπαρίστανται με \(24\) και \(8\) bit αντίστοιχα. Αυτού του είδους η λύση λέγεται floating point arithmetic, καθώς όσο μεγαλύτερος είναι ο αριθμός, τόσο λιγότερο ακριβής ο υπολογισμός. Σκεφτείτε ότι το \(x\) είναι τα ψηφία του αριθμού, και το \(y\) καθορίζει πού θα μπει η υποδιαστολή. Έτσι αν η υποδιαστολή μπει πολύ αριστερά, θα έχουμε μεγάλο δεκαδικό μέρος (μεγάλη ακρίβεια) αλλά μικρό ακέραιο μέρος (μικρός αριθμός), ενώ αν η υποδιαστολή μπει πολύ δεξιά θα έχουμε μεγάλο αριθμό αλλά με μικρή ακρίβεια. Προτιμούμε αυτή τη μέθοδο, διότι δεν έχει μεγάλη διαφορά αν αναπαριστώντας την ταχύτητα του φωτός χάσουμε 1χλμ/ώρα, αλλά έχει μεγάλη διαφορά αν αναπαριστώντας το μέγεθος ενός μορίου χάσουμε 1 εκατοστό. Αυτή η λύση είναι καλή για ταχείες προσομοιώσεις φυσικής, όπου χρειαζόμαστε γρήγορους υπολογισμούς, αλλά οι έλεγχοι ισότητας σπανίζουν.

Μια λύση για ακριβείς μαθηματικούς υπολογισμούς είναι το arbitrary precision arithmetic, το οποίο χρησιμοποιεί όση μνήμη χρειάζεται για να γραφεί ο αριθμός ως αριθμητής και παρονομαστής για να αναπαρασταθούν οι ρητοί αριθμοί, αλλά είναι συγκριτικά πολύ πιο αργό από τις άλλες δύο λύσεις.