Ο Στέργιος μόλις έμαθε πρόσθεση και αφαίρεση στο σχολείο και βρήκε ένα καινούριο παιχνίδι: διαλέγει στην τύχη τρεις αριθμούς, π.χ., το \((1, 2, 6)\) και σε κάθε βήμα μπορεί να αντικαταστήσει έναν από αυτούς (όποιον θέλει—έστω το 2) με το άθροισμα των άλλων (\(1 + 6\)) δύο φορές μείον τον εαυτό του (\(1 + 6 + 1 + 6 - 2 = 12\)) και παίρνει μια καινούρια τριάδα \((1, 12, 6)\). Αναρωτιέται αν κάνοντας τέτοια βήματα / επιλογές επανειλημμένα θα καταφέρει να μηδενίσει έναν από τους αριθμούς. Πέρα από αυτό, αναρωτιέται αν μπορεί να βρει την συντομότερη σειρά επιλογών προκειμένου να μηδενίσει έναν εξ αυτών. Με δοκιμές παρατήρησε ότι για τους αριθμούς \((1, 2, 6)\) η καλύτερη επιλογή είναι να διαλέξει το 6 πρώτα καθώς σε μόνο ένα βήμα θα πάρει την τριάδα \((1, 2, 0)\).
Έστω stergios η μαγική συνάρτηση που δίνει τον ελάχιστο αριθμό βημάτων προκειμένου να
μηδενιστεί ένας από τους αριθμούς της αρχικής τριάδας. Για παράδειγμα,
\(stergios(0, 7, 9) = 0\), \(stergios(1, 2, 6) = 1\), \(stergios(1000, 216, 102) = 3\) (πως;). Αν
δεν υπάρχει αριθμός βημάτων που να την μηδενίζει, τότε η συνάρτηση stergios πάλι
επιστρέφει μηδέν. Για παράδειγμα, \(stergios(74, 214, 540) = 0\) (ο Στέργιος δεν βρήκε κάποιον
τρόπο να φτάσει στο μηδέν με αυτούς τους τρεις αριθμούς όσο και αν προσπάθησε). Είναι εφικτό
να υπολογίσουμε αθροίσματα της συνάρτησης stergios για όλους τους αριθμούς αν κάποιες από
τις αρχικές μας επιλογές είναι μεγάλοι ακέραιοι; Συγκεκριμένα, ο Στέργιος αναρωτιέται αν
μπορούμε να υπολογίσουμε το άθροισμα:
Ο μπαμπάς του, ο Μάκης, προσπάθησε, πρώτα μόνος και μετά με βοήθεια, αλλά δεν μπόρεσε να
δώσει μια ικανοποιητική απάντηση. Μήπως μπορείτε εσείς; Τα τελευταία βράδια ο Μάκης βλέπει
διαρκώς στο όνειρό του ότι \(\sum_{i=0}^{\infty} stergios(1000, 216, i) = 1051\) και επίσης πως
\(stergios(1000, 216, 109218) = 108\) αλλά δεν έχει καμία βεβαιότητα. Το μόνο που ξέρει είναι
πως η τιμή του \(Solution\) τυχαίνει να είναι και το password του χρήστη impossible0 στο
σύστημα 35.169.96.19 της Εργασίας 0.
Η πρώτη σωστή λύση στον παραπάνω γρίφο θα οδηγήσει σε Bonus μέχρι 360 μονάδες. Οι επόμενες λύσεις θα λάβουν επίσης bonus αναλογικά (η 2η μέχρι 360/2=180 μονάδες, η 3η μέχρι 360/3=120 μονάδες κοκ). Το πρόβλημα θα κλείσει μόλις (εάν) βρεθούν 10 λύσεις ή τελειώσει το εξάμηνο—ότι από τα δύο συμβεί πιο γρήγορα.
Ξεκίνα με ένα πρόγραμμα ωμής βίας (αναζήτηση κατά πλάτος στις τριάδες) για μικρούς αριθμούς
και επιβεβαίωσε τα παραδείγματα και τις «ονειρικές» τιμές του Μάκη· μετά ψάξε δομή στα
αποτελέσματα. Παρατήρησε ότι το βήμα \(x \to 2(y+z) - x\) είναι «ανάκλαση» και ότι κάνοντάς το
δύο φορές στην ίδια θέση επιστρέφεις εκεί που ήσουν· σκέψου ποια ποσότητα των τριών αριθμών
μένει αναλλοίωτη και ποιο βήμα μικραίνει την τριάδα, ώστε να μην εξερευνάς τυφλά. Το
άθροισμα είναι άπειρο αλλά μόνο πεπερασμένα \(i\) δίνουν μη μηδενικό αποτέλεσμα, και οι τιμές
ξεπερνούν τα 64 bits, άρα χρειάζεσαι προσοχή με τους τύπους (π.χ. __int128 ή δική σου
αριθμητική).
Αριθμός στον οδηγό: Α16.18
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: hw-2025-bonus0-stergios ·
Σύνδεσμος: https://progintro.github.io/study/questions/homework/hw-2025-bonus0-stergios.html ·
Markdown (GitHub)