Δύο ορειβάτες προσπαθούν να φτάσουν στην πιο ψηλή κορυφή μιας οροσειράς. Ο πρώτος ξεκινά από δυτικά και κατευθύνεται ανατολικά, ενώ ο δεύτερος ξεκινά από ανατολικά και κατευθύνεται δυτικά. Η ανάβαση σε μία κορυφή είναι πάντοτε δυσκολότερη και απαιτεί τρεις ώρες, ενώ η κατάβαση είναι ευκολότερη και απαιτεί μόνο μία ώρα, για οποιοδήποτε υψόμετρο. Αν σας δοθούν το πλήθος και τα ύψη όλων των κορυφών της οροσειράς, να βρείτε τον συνολικό χρόνο που θα κάνει ο ορειβάτης, ο οποίος θα φτάσει γρηγορότερα στην ψηλότερη κορυφή της οροσειράς.
Για παράδειγμα, αν έχουμε την πιο κάτω οροσειρά:
Ο ορειβάτης Α θα χρειαστεί 3 ώρες για να ανέβει στην κορυφή με υψόμετρο 67, άλλες 3 ώρες για να ανέβει στην κορυφή με υψόμετρο 345, άλλη μία ώρα για να κατέβει στην κορυφή με υψόμετρο 189 και άλλες 3 ώρες για να ανέβει στην ψηλότερη κορυφή με υψόμετρο 567. Συνολικός χρόνος: 10 ώρες
Ο ορειβάτης Β θα χρειαστεί 3 ώρες για να ανέβει στην κορυφή με υψόμετρο 432, άλλες 3 ώρες για να ανέβει στην κορυφή με υψόμετρο 512, άλλη μία ώρα για να κατέβει στην κορυφή με υψόμετρο 201, άλλες 3 ώρες για να ανέβει στην κορυφή με υψόμετρο 345 και άλλες 3 ώρες για να ανέβει στην ψηλότερη κορυφή με υψόμετρο 567. Συνολικός χρόνος: 13 ώρες.
Δεδομένα εισόδου
Δεδομένα εξόδου
Ο ελάχιστος συνολικός χρόνος που θα χρειαστεί ο ορειβάτης, ο οποίος θα ανέβει γρηγορότερα στην ψηλότερη κορυφή της οροσειράς. Να θεωρήσετε ότι πάντοτε κάποιος θα φτάνει γρηγορότερα.
Η επεξήγηση του παραδείγματος φαίνεται στην εικόνα πιο πάνω.