18ος ΠΔΠ Γ' Φάση
Κυκλικός Επιταχυντής (cyclotron)
[25 Μονάδες]
Οι συμμετέχοντες στο camp του 18ου ΠΔΠ, επισκέφθηκαν το νέο Κυκλικό Επιταχυντή Στοιχειωδών Σωματείων (ΚΕΣΣ) Θεσσαλονίκης. Ο επιταχυντής αυτός, περιλαμβάνει \(N\) θυρίδες εισόδου σωματείων. Στην είσοδο κάθε θυρίδας τα σωμάτια λαμβάνουν ενέργεια \(E^{\text{in}}(N)\) (όπου \(N\) ο αριθμός της θυρίδας). Κατά την τροχιά τους μέχρι την επόμενη θυρίδα, τα σωμάτια, δαπανούν ενέργεια που αντιστοιχεί σε φράγμα δυναμικού \(Ε^{\text{out}}(N)\) που πρέπει να «υπερπηδήσουν». Αν \(E^{\text{in}}(N) \geq E^{\text{out}}(N)\) το σωμάτιο θα φθάσει στην επόμενη θυρίδα (\(N+1\)), στην οποία και θα λάβει ενέργεια \(E^{\text{in}}(N+1)\). Η συνολική λοιπόν ενέργεια του σωματίου στην \(N+1\) θυρίδα (εφόσον μπήκε στην \(Ν\)) θα είναι: (\(E^{\text{in}}(N) - E^{\text{out}}(N) ) + E^{\text{in}}(N+1)\).
Πρόβλημα
Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα προσδιορίζει την πρώτη (με το μικρότερο αριθμό) θυρίδα από την οποία αν εισέλθει το σωμάτιο, θα ολοκληρώσει μια πλήρη κυκλική τροχιά εντός του επιταχυντή.
Αρχεία εισόδου
Το αρχείο cyclotron.in στην πρώτη γραμμή έχει έναν ακέραιο αριθμό που δηλώνει τον αριθμό των θυρίδων εισόδου \(N\), όπου: (\(10 \leq N \leq 2.000.000\)). Στις επόμενες \(N\) γραμμές δίδονται από δύο ακέραιοι αριθμοί \(X\), \(Y\) που ξεχωρίζουν με ένα κενό (\(0 \leq X, Y \leq 1.000\)). Ο πρώτος αριθμός κάθε γραμμής, (\(X\)) δίνει την ενέργεια (σε eV) που παρέχεται στο σωμάτιο με την είσοδό του στη θυρίδα και ο δεύτερος αριθμός, (\(Y\)) δίνει την ενέργεια που δαπανά το σωμάτιο μέχρι την επόμενη θυρίδα.
Αρχεία εξόδου
Το αρχείο cyclotron.out αποτελείται από έναν ακέραιο που αντιστοιχεί στον αριθμό της θυρίδας από την οποία πρέπει να ξεκινήσει το σωμάτιο ώστε να ολοκληρώσει μια πλήρη κυκλική τροχιά εντός του επιταχυντή. Εάν δεν υπάρχει κατάλληλη θυρίδα εισόδου θα επιστρέφεται ο αριθμός 0.
Παραδείγματα αρχείων εισόδου - εξόδου
1o
| cyclotron.in | cyclotron.out |
|---|---|
| 10 50 100 120 100 90 100 140 100 90 90 90 90 90 90 90 90 90 90 90 90 |
2 |
Περιορισμοί
- Μέγιστος χρόνος εκτέλεσης: 4 δευτερόλεπτα για κάθε τεστ.