29ος ΠΔΠ Καμπ (seniors)
Εξωγήινες συχνότητες (aliens)

Είμαστε στο έτος 2026 και επιτέλους έχει ανακαλυφθεί ένας ραδιοφωνικός πομπός που μπορεί να στέλνει σήματα σε εξωγήινους! Δυστυχώς, δεν είναι γνωστή η ακριβής συχνότητα στην οποία λειτουργούν οι εξωγήινοι δέκτες. Έστω ότι οι συχνότητες είναι φυσικοί αριθμοί που δεν υπερβαίνουν το \(10^9\). Είναι γνωστό ότι η σωστή συχνότητα είναι μία από \(N\) δεδομένες συχνότητες \(f_i\) (\(1 \leq i \leq N\)) σε αυτό το διάστημα, οπότε οι επιστήμονες πρέπει να στείλουν ένα μήνυμα σε κάθε μία από αυτές για να είναι βέβαιοι ότι οι εξωγήινοι θα το λάβουν.

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

Να αυξηθεί ή να μειωθεί η συχνότητα κατά \(1\). Στην περίπτωση αυτή, ο πομπός υπερφορτίζεται και η θερμοκρασία του πομπού αυξάνει κατά \(1\) βαθμό Κελσίου. Η πράξη αυτή απαιτεί 1 δευτερόλεπτο για να εκτελεστεί.
Να αυξηθεί ή να μειωθεί η συχνότητα κατά \(2\). Στην περίπτωση αυτή, η θερμοκρασία του πομπού δεν μεταβάλλεται, αλλά η πράξη αυτή απαιτεί \(2\) δευτερόλεπτα για να εκτελεστεί.

Ο πομπός λειτουργεί κάπου στην Ανταρκτική και η αρχική του θερμοκρασία είναι \(0\) βαθμοί Κελσίου. Αν η θερμοκρασία του υπερβεί τους \(T\) βαθμούς, τότε ο πομπός καταστρέφεται. Αυτό δεν πρέπει να συμβεί γιατί ο πομπός είναι πανάκριβος.

Γράψτε ένα πρόγραμμα που να υπολογίζει τον ελάχιστο χρόνο που απαιτείται για να εκπέμψουν οι επιστήμονες σε όλες τις \(N\) δοθείσες συχνότητες. Θεωρήστε ότι η εκπομπή ενός μηνύματος δεν απαιτεί χρόνο (μόνο η αύξηση ή η μείωση της συχνότητας του πομπού).

Δεδομένα εισόδου (aliens.in)

Η πρώτη γραμμή της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(N\) και \(T\) χωρισμένους με ένα κενό διάστημα: το πλήθος \(N\) των συχνοτήτων που πρέπει να δοκιμαστούν και τη μέγιστη θερμοκρασία \(T\) λειτουργίας του πομπού. Η δεύτερη γραμμή θα περιέχει \(N\) φυσικούς αριθμούς χωρισμένους ανά δύο με ένα κενό διάστημα: τις συχνότητες \(f_i\) (\(1 \leq i \leq N\)) που πρέπει να δοκιμαστούν. Οι συχνότητες θα είναι διαφορετικές και θα δίνονται σε αύξουσα σειρά.

Δεδομένα εξόδου (aliens.out)

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

Παράδειγμα αρχείων εισόδου - εξόδου

aliens.in	aliens.out
4 2 3 5 6 9	12

Εξήγηση: Με μία δυνατή ακολουθία πράξεων, ο πομπός μπορεί να περάσει διαδοχικά από τις εξής συχνότητες: \(0, 2, 3, 5, 7, 9, 8, 6\). (Οι αντίστοιχες πράξεις ήταν \(+2, +1, +2, +2, +2, −1, −2\).) Στο τέλος της, η θερμοκρασία του πομπού είναι \(2\). Η ακολουθία αυτή περνά από όλες τις δοθείσες συχνότητες και απαιτεί \(12\) δευτερόλεπτα. Δεν υπάρχει τρόπος να επιτευχθεί ο σκοπός σε λιγότερα από \(12\) δευτερόλεπτα.

Περιορισμοί

Mέγιστος χρόνος εκτέλεσης: \(2\) sec.
Mέγιστη διαθέσιμη μνήμη: \(64\) MB.

Υποπροβλήματα