Mηνιαία Πρόκληση: Φεβρουάριος 2021
Δημοσιεύτηκε: Σάβ Ιαν 30, 2021 7:56 pm
Συνεχίζουμε με τις μηνιαίες προκλήσεις, και μπαίνουμε στον Φεβρουάριο.
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Μαρτίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Ιανουαρίου έχει επιλεγεί ήδη ο Κώστας (εγώ) ως βοηθός Φεβρουαρίου.
Σε αυτό το πρόβλημα θέλουμε να διακοσμήσουμε ένα πάρτι με μπαλόνια. Έχουμε μία μεγάλη ευθεία, και Ν μπαλόνια. Για κάθε μπαλόνι ξέρουμε την Χ συντεταγμένη όπου βρίσκεται, και τη μέγιστη ακτίνα που μπορεί να αποκτήσει πριν σκάσει (μπορούμε να το φουσκώσουμε και λιγότερο, προφανώς).
Ο τρόπος με τον οποία τα φουσκώνουμε είναι ο εξής. Ξεκινάμε από τα αριστερά προς τα δεξιά και φουσκώνουμε κάθε μπαλόνι όσο το δυνατόν περισσότερο γίνεται (μέχρι να φτάσει τη μέγιστη ακτίνα του, ή να ακουμπήσει κάποιο άλλο ήδη φουσκωμένο μπαλόνι).
Παρατήρηση: τα μπαλόνια δεν θα έχουν κέντρα στην ίδια ευθεία αλλά αρχές (κατώτατο σημείο) στην ίδια ευθεία και έτσι πρέπει να σκεφτείτε και για τις δύο διαστάσεις, όπως σε αυτή την εικόνα.
Ζητείται να τυπώσουμε την ακτίνα κάθε μπαλονιού μετά το τέλος της διαδικασίας μας.
Στο input θα μας δίνεται το Ν (πλήθος μπαλονιών), και θα ακολουθούν Ν δυάδες αριθμών. Ο πρώτος αριθμός της i-οστής δυάδας είναι η Χ συντεταγμένη του i-οστού μπαλονιού, και ο δεύτερος η μέγιστη ακτίνα του. Τα μπαλόνια θα δίνονται ταξινομημένα ως προς την Χ συντεταγμένη τους.
Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την παραπάνω εικόνα) :
3
0 9
8 1
13 7
Θά έπρεπε να βρούμε:
9.000
1.000
4.694
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ.: Μετά από λίγη ενασχόληση με το πρόβλημα, θα δείτε ότι απαραίτητη υπορουτίνα για τη λύση του είναι η εξής: Δίνεται ένα φουσκωμένο μπαλόνι Α (με αρχή χ και ακτίνα r), πόσο μπορώ να φουσκώσω ένα δεύτερο μπαλόνι Β (με αρχή x') μέχρι να ακουμπήσουν;
Το πρόβλημα αυτό μπορεί να λυθεί με μαθηματικά Β' Λυκείου, σε Ο(1) χρόνο. Αν δεν γνωρίζετε πώς, θα σας δώσουμε τον κώδικα στις 15 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!
Κάθε αρχή του μήνα θα ανεβαίνει στο pdpforum ένα πρόβλημα προς συζήτηση.
Στα σχόλια μπορεί να ξεκινήσει συζήτηση εάν έχετε κάποια απορία για το πρόβλημα, ή κάποια παρατήρηση, οσοδήποτε απλή, που πιστεύετε μπορεί να βοηθήσει αλλά δεν ξέρετε πώς.
Οι απαντήσεις και οι παρατηρήσεις ας μπαίνουν σε spoiler tags βέβαια!
Περίπου στο τέλος του μήνα θα δίνεται ένα link για σύσκεψη στην οποία θα συζητάμε όλοι μαζί το πρόβλημα, τις λύσεις μας, πιθανές βελτιώσεις, κλπ.
Σημείωση: Ένας από τους συμμετέχοντες της σύσκεψης θα επιλέγεται ώστε να βοηθήσει τον Βαγγέλη με την επόμενη μηνιαία πρόκληση, αυτή του Μαρτίου εν προκειμένω.
Οι αρμοδιότητές του θα είναι να λύσει το επόμενο πρόβλημα εντός του μήνα (εννοείται με συνεννόηση/βοήθεια από τον Βαγγέλη) ώστε να είναι σε θέση να λύνει απορίες στην επόμενη σύσκεψη και στο forum.
(Και πάλι, εννοείται θα είναι κι o Βαγγέλης στη σύσκεψη, οπότε δεν αγχωνόμαστε "Τι θα γίνει αν δε μπορώ να απαντήσω σε κάποια ερώτηση;").
Από τη σύσκεψη Ιανουαρίου έχει επιλεγεί ήδη ο Κώστας (εγώ) ως βοηθός Φεβρουαρίου.
Σε αυτό το πρόβλημα θέλουμε να διακοσμήσουμε ένα πάρτι με μπαλόνια. Έχουμε μία μεγάλη ευθεία, και Ν μπαλόνια. Για κάθε μπαλόνι ξέρουμε την Χ συντεταγμένη όπου βρίσκεται, και τη μέγιστη ακτίνα που μπορεί να αποκτήσει πριν σκάσει (μπορούμε να το φουσκώσουμε και λιγότερο, προφανώς).
Ο τρόπος με τον οποία τα φουσκώνουμε είναι ο εξής. Ξεκινάμε από τα αριστερά προς τα δεξιά και φουσκώνουμε κάθε μπαλόνι όσο το δυνατόν περισσότερο γίνεται (μέχρι να φτάσει τη μέγιστη ακτίνα του, ή να ακουμπήσει κάποιο άλλο ήδη φουσκωμένο μπαλόνι).
Παρατήρηση: τα μπαλόνια δεν θα έχουν κέντρα στην ίδια ευθεία αλλά αρχές (κατώτατο σημείο) στην ίδια ευθεία και έτσι πρέπει να σκεφτείτε και για τις δύο διαστάσεις, όπως σε αυτή την εικόνα.
Ζητείται να τυπώσουμε την ακτίνα κάθε μπαλονιού μετά το τέλος της διαδικασίας μας.
Στο input θα μας δίνεται το Ν (πλήθος μπαλονιών), και θα ακολουθούν Ν δυάδες αριθμών. Ο πρώτος αριθμός της i-οστής δυάδας είναι η Χ συντεταγμένη του i-οστού μπαλονιού, και ο δεύτερος η μέγιστη ακτίνα του. Τα μπαλόνια θα δίνονται ταξινομημένα ως προς την Χ συντεταγμένη τους.
Ζητείται αλγόριθμος είτε Ο(ΝlogN) είτε Ο(Ν).
Παράδειγμα (ίδιο με την παραπάνω εικόνα) :
3
0 9
8 1
13 7
Θά έπρεπε να βρούμε:
9.000
1.000
4.694
Στις 15 του μηνός θα δώσουμε ένα hint, θυμίστε το μας αν το ξεχάσουμε.
Καλή επιτυχία!
Υ.Γ.: Μετά από λίγη ενασχόληση με το πρόβλημα, θα δείτε ότι απαραίτητη υπορουτίνα για τη λύση του είναι η εξής: Δίνεται ένα φουσκωμένο μπαλόνι Α (με αρχή χ και ακτίνα r), πόσο μπορώ να φουσκώσω ένα δεύτερο μπαλόνι Β (με αρχή x') μέχρι να ακουμπήσουν;
Το πρόβλημα αυτό μπορεί να λυθεί με μαθηματικά Β' Λυκείου, σε Ο(1) χρόνο. Αν δεν γνωρίζετε πώς, θα σας δώσουμε τον κώδικα στις 15 του μηνός, μέχρι τότε προσποιηθείτε ότι γνωρίζετε πώς λύνεται!