37ος ΠΔΠ Α' Φάση: Πολύγωνο κουτιών (polybox) - Λύση

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

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

Παρατήρηση: Είναι φανερό ότι όλα τα ύψη \(h_i\) συμμετέχουν στο μήκος του περιγράμματος και μάλιστα κάθε ύψος \(h_i\) συμμετέχει δύο φορές στο περίγραμμα (για την αριστερή και δεξιά πλευρά του ορθογωνίου παραλληλογράμμου \(i\)). Στο περίγραμμα συμμετέχουν αυτούσια επίσης, το πλάτος \(w_1\) και το πλάτος \(w_n\), δηλαδή η βάση του χαμηλότερου και η οροφή του υψηλότερου παραλληλογράμμου.

Η παραπάνω παρατηρήση αρκεί για να υπολογιστεί η απάντηση για το υποπρόβλημα \(1\) (όπου όλα τα πλάτη είναι ίσα), καθώς το περίγραμμα που σχηματίζεται από όλα τα κουτιά είναι πάλι ένα ορθογώνιο παραλληλόγραμμο με πλάτος \(w_1=w_2=\dots=w_n\) και ύψος \(h_1+h_2+\dots+h_n\). Η απάντηση για το πρώτο υποπρόβλημα είναι \(2\cdot w_1 + 2\cdot(h_1+h_2+\dots+h_n)\).

Για το δεύτερο υποπρόβλημα παρατηρούμε ότι υπάρχει και κάποιο επιπλέον τμήμα που αυξάνει το περίγραμμα στην επαφή των δύο κουτιών όπου το πλάτος \(w_2\) δεν καλύπτεται από το \(w_1\) (βλέπε ακόλουθο σχήμα). Είναι φανερό ότι δεν έχει σημασία αν τα κουτιά είναι στοιβαγμένα στον κεντρικό άξονα συμμετρίας ή στη μια πλευρά, καθώς από την πλευρά που έχουν κοινή τα δύο κουτιά, συμμετέχει στο περίγραμμα το \(w_2-w_1\) δηλαδή η διαφορά της μεγαλύτερης βάσης από τη μικρότερη βάση.

Με την παρατήρηση αυτή μπορούμε να λύσουμε και το επόμενο υποπρόβλημα με τα πολλά κουτιά, όπου ανάμεσα σε δυο οποιαδήποτε διαδοχικά κουτιά μπορούμε να υπολογίσουμε το τμήμα που συμμετέχει στο τελικό περίγραμμα.

    //υπολόγισε στη μεταβλητή ans την πιο πάνω και την πιο κάτω πλευρά της στοίβας
    ll ans = w[0] + w[N-1];
    //πρόσθεσε στη ans όλα τα ενδιάμεσα εκτεθειμένα τμήματα
    for(long i=0;i<N-1;i++)
        ans += abs(w[i]-w[i+1]);
    //πρόσθεσε τα ύψη όλων των κουτιών
    for(long i=0;i<N;i++)
        ans += h[i]*2;
    printf("%lld\n",ans);

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

Πλήρης λύση με χρήση μεγάλων αριθμών

Για να λυθεί και το τελευταίο υποπρόβλημα θα χρειαστεί να υλοποιήσουμε κάποια δομή ακεραίων που να υποστηρίζει ακέραιους αριθμούς που ξεπερνούν το \(10^{45}\) (το μέγιστο ύψος \(10^{40}\) επί τον μέγιστο αριθμό κουτιών \(10^5\))

Μια εύκολη λύση είναι να αποθηκεύσουμε τα ψηφία των αριθμών σε κάποιο πίνακα ακεραίων και να κάνουμε τις πράξεις όπως μάθαμε στο δημοτικό σχολείο. Για την αποθήκευση των αριθμών (οι οποίοι δεν έχουν σταθερό αριθμό ψηφίων) μπορούμε να χρησιμοποιήσουμε τη δομή vector<int> της C++. Στη θέση \(0\) στο vector θα αποηκεύουμε το ψηφίο των μονάδων, στη θέση \(1\) το ψηφίο των δεκάδων κλπ. Το vector θα επεκτείνεται ώστε να χωρά ακριβώς τα ψηφία του αριθμού που θα περιέχει.

Η C++ επιτρέπει να ορίσουμε πράξεις και συγκρίσεις στα vector μας. Για τις συγκρίσεις των μεγάλων αριθμών δημιουργήθηκε η βοηθητική συνάρτηση cmp(a,b), η οποία επιστρέφει \(-1\) όταν \(a\lt b\), \(0\) αν \(a=b\) και \(+1\) όταν \(a\gt b\). Η σύγκριση γίνεται κατά τα γνωστά, πρώτα με το μήκος των αριθμών (ο αριθμός με τα λιγότερα ψηφία είναι ο μικρότερος) και σε περίπτωση ίδιου μήκους τότε συγκρίνουμε ένα ένα τα ψηφία ξεκινώντας από το ψηφίο με το μεγαλύτερο βάρος μέχρι να βρούμε ασυμφωνία, οπότε ο αριθμός με το μικρότερο ψηφίο είναι ο μικρότερος.

int cmp(const bigint& a,const bigint& b){
    if(a.size()<b.size())return -1;
    if(b.size()<a.size())return 1;
    for(int i=a.size()-1;i>=0;i--){
        if(a[i]<b[i])return -1;//a<b
        if(a[i]>b[i])return 1;//a>b
    }
    return 0;//a==b
}

ο κώδικας για τις συγκρίσεις ακολουθεί:

bool operator < (const bigint& a,const bigint& b){
    return cmp(a,b)<0;
}

bool operator == (const bigint& a,const bigint& b){
    return cmp(a,b)==0;
}

bool operator <= (const bigint& a,const bigint& b){
    return cmp(a,b)<=0;
}

Η πράξη της πρόσθεσης μεταξύ δύο αριθμών, ξεκινά από τις μονάδες (τυχόν κρατούμενα θα παραμείνουν για να προστεθούν στις δεκάδες) κλπ.

bigint operator +(const bigint& a,const bigint& b){
    bigint c;
    int remain=0;
    for(int i=0;remain or i<a.size() or i<b.size();i++){
        int result = remain;
        if(i<a.size()) result += a[i];
        if(i<b.size()) result += b[i];
        c.push_back(result % 10);
        remain = result / 10;
    }
    return c;
}

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

bigint operator - (const bigint& a,const bigint& b){
    //προσοχή λειτουργεί σωστά μόνο όταν a>=b
    assert(b<=a);
    bigint c;
    int remain = 0;
    for(int i=0;i<a.size() or i<b.size();i++){
        if(i<b.size())remain += b[i];
        ll result = -remain;
        if(i<a.size()) result += a[i];
        remain = 0;
        if(result<0){//έχουμε κρατούμενο
            remain++;
            result+=10;
        }
        assert(result<10);
        c.push_back(result);
    }
    return c;
}

Θα χρειαστούν και οι αντίστοιχες συναρτήσεις ανάγνωσης και εκτύπωσης μεγάλων αριθμών στα αρχεία εισόδου-εξόδου:

void read(bigint& a){
    char s[45];
    scanf(" %s",s);
    a.clear();
    for(int i=strlen(s)-1;i>=0;i--)
        a.push_back(s[i]-'0');
}

void write(const bigint& a){
    printf("%d",a.size()==0?0:a[a.size()-1]);
    for(int i=a.size()-2;i>=0;i--)
        printf("%0d",a[i]);
}

Η πολυπλοκότητα είναι \(\mathcal{O}(N\cdot c)\), όπου \(c\) το πλήθος των ψηφίων του μεγαλύτερου αριθμού (το πολύ \(40\)). Δείτε ολόκληρο τον κώδικα εδώ.

Σημείωση: Αντί να χρησιμοποιήσουμε το δεκαδικό σύστημα αρίθμησης, μπορούμε να χρησιμοποιήσουμε οποιοδήποτε άλλο σύστημα με βάση \(10^k\) ώστε να περιορίσουμε τον αριθμό των ψηφίων του μεγάλου αριθμού. Το \(10^k\) πρέπει να χωρά σε έναν τύπο ακεραίου του υπολογιστή, οπότε \(k\le9\) για ακεραίους 32bit. Τον κώδικα που προέκυψε με τροποποιήσεις της προηγούμενης λύσης, κυρίως στην ανάγνωση και εκτύπωση των αριθμών στα αρχεία εισόδου-εξόδου, μπορείτε να τον δείτε εδώ.

Πλήρης λύση με BigInt της Java

Αξίζει να σημειωθεί ότι η Java έχει υπσοτήριξη για μεγάλους ακεραίους με τους τύπους BigInteger. Επομένως, μία λύση που περνάει όλα τα testcases είναι η εξής:

   public static void main(String[] arguments) throws Exception {
      Scanner sc = new Scanner(new FileInputStream("polybox.in"));
       
      int subtask = sc.nextInt();
      int N = sc.nextInt();
      ArrayList<BigInteger> w = new ArrayList<>(), h = new ArrayList<>();
      for (int i = 0; i < N; ++i) {
         w.add(sc.nextBigInteger());
         h.add(sc.nextBigInteger());
      }
      
      //υπολόγισε στη μεταβλητή ans την πιο πάνω και την πιο κάτω πλευρά της στοίβας
      BigInteger ans = w.get(0).add(w.get(N-1));
      //πρόσθεσε στη ans όλα τα ενδιάμεσα εκτεθημένα τμήματα
      for(int i=0;i<N-1;i++)
         ans = ans.add(w.get(i).subtract(w.get(i+1)).abs());
      //πρόσθεσε τα ύψη όλων των κουτιών
      BigInteger two = new BigInteger("2");
      for(int i=0;i<N;i++)
        ans = ans.add(h.get(i).multiply(two));
 
      PrintWriter out = new PrintWriter(new File("polybox.out"));
      out.println(ans);
      out.close();
   }

Δείτε τον πλήρη κώδικα εδώ.