Αρχική > 18ος ΠΔΠ

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 δευτερόλεπτα για κάθε τεστ.