Το επόμενο ζήτημα (εξαιρετικά όμορφο
) αποτελεί ΘΕΜΑ Β' ΦΑΣΗΣ του 17ου Πανελλήνιου Διαγωνισμού Πληροφορικής.
Πληροφορίες θα πάρετε από το δικτυακό τόπο
http://www.pdp.gr/
Παρακαλείστε ιδιαίτερα να μην δημοσιεύσετε τις απαντήσεις σας στο Ασκησιολόγιο της Γλωσσομάθειας
μέχρι τις 28 Φεβρουαρίου 2005, όπου λήγει η Β΄ φάση του Π.Δ.Π.
Εώς τότε προσπαθήστε με την ησυχία σας.
ΔΗΜΟΚΡΙΤΟΣ
Το Εθνικό Κέντρο Έρευνας Φυσικών Επιστημών "Δημόκριτος" της Ελλάδος, ονομάστηκε έτσι προς τιμή του Έλληνα «πατέρα» της ατομικής θεωρίας Δημόκριτου. Το Ε.Κ.Ε.Φ.Ε. διαθέτει πολλά Ερευνητικά Ινστιτούτα με περισσότερο ίσως γνωστό, το Ινστιτούτο Πυρηνικών Ερευνών. Μια από τις πολλές δραστηριότητες αυτού του Ινστιτούτου, είναι η παραγωγή ραδιενεργών σκευασμάτων που χρησιμοποιούνται για θεραπευτικούς, ερευνητικούς και παραγωγικούς σκοπούς. (π.χ. Ραδιοθεραπείες, Ισοτοπική Επισήμανση, Βιομηχανικές Ακτινογραφίες).
Τα ραδιενεργά σκευάσματα, τοποθετούνται σε ειδικά κιβώτια που δεν επιτρέπουν την εκπομπή ακτινοβολίας μέσα από αυτά. Κάθε κιβώτιο είναι εφοδιασμένο με συσκευή εκπομπής αναγνωριστικού σήματος (ραδιοταυτότητα). Τα κιβώτια αποθηκεύονται σε συγκεκριμένες θέσεις μιας επίπεδης αποθήκης. Μεταξύ των θέσεων αποθήκευσης, σχηματίζεται ένα κανονικό τετραγωνικό πλέγμα από διαδρόμους μετακίνησης. Ο κάθε κόμβος (διασταύρωση) των διαδρόμων μετακίνησης, προσδιορίζεται από ζεύγος συντεταγμένων (x, y). Στην οροφή της αποθήκης και στις «διασταυρώσεις» αυτού του πλέγματος, είναι τοποθετημένοι αισθητήρες υπερβραχέων, με σκοπό την αναγνώριση της θέσης των κιβωτίων. Ο κάθε αισθητήρας έχει συντεταγμένες (x, y) και ένα μοναδικό κωδικό αριθμό, που απεικονίζεται στο σύστημα ελέγχου. Αν ένα κιβώτιο βρεθεί σε μία διασταύρωση (κόμβο), τότε γίνεται αντιληπτό από το αισθητήρα που βρίσκεται ακριβώς πάνω από τον κόμβο και από τους οκτώ πλησιέστερους αισθητήρες προς το συγκεκριμένο κόμβο. Για παράδειγμα ένα κιβώτιο που θα περάσει από τη θέση (0, 0) γίνεται αντιληπτό από τους αισθητήρες: (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1) και τον (0, 0).
Τα κιβώτια μετακινούνται εντός της αποθήκης, με τη βοήθεια αυτόματου ρομποτικού οχήματος μεταφοράς. Προφανώς το ρομπότ μπορεί να μετακινείται στους διαδρόμους μεταξύ των κιβωτίων, κινούμενο πάντοτε παράλληλα ή κάθετα στον άξονα των x. Το ρομπότ ευρισκόμενο σε κάποιο κόμβο, μπορεί να κάνει μια από τις τέσσερις κινήσεις (Up), (Down), (Right), (Left). Κάθε κίνηση R αυξάνει τη τιμή της συντεταγμένης x (τετμημένη) κατά 1. Κάθε κίνηση U αυξάνει τη τιμή της συντεταγμένης y (τεταγμένη) κατά 1. Ως αρχή των κινήσεων του ρομποτικού συστήματος μεταφοράς, νοείται πάντοτε η αρχή των αξόνων (0,0).
Στο επόμενο σχήμα, δίνεται ένα απλοποιημένο διάγραμμα διαδρομών με (11 x 11) διασταυρώσεις.
Να αναπτύξετε ένα πρόγραμμα το οποίο θα λαμβάνει σαν είσοδο τις κινήσεις των κιβωτίων και θα παράγει σαν έξοδο:
Α) Mε αύξουσα σειρά, τους κωδικούς αριθμούς των αισθητήρων που αναγνώρισαν τα κιβώτια.
Β) Τον αριθμό των διεγέρσεων που δέχθηκε κάθε αισθητήρας.
ΔΕΔΟΜΕΝΑ ΕΙΣΟΔΟΥ - ΕΞΟΔΟΥ
Δεδομένα Εισόδου
Στην πρώτη γραμμή του αρχείου εισόδου dimokritos.in δίνεται ένας ακέραιος αριθμός N, (όπου 1 < N < 2,000,000), που αντιπροσωπεύει το πλήθος των αισθητήρων. Σε κάθε μία από τις ακόλουθες N γραμμές δίνονται οι συντεταγμένες των αισθητήρων με δύο ακέραιους αριθμούς, Χ και Υ που χωρίζονται με κενό χαρακτήρα, ( όπου -700 < x, y < 700). Η σειρά εμφάνισης των αισθητήρων ταυτίζεται με τον αντίστοιχο κωδικό αριθμό τους.
Στην επόμενη, (N+1)οστή γραμμή, δίνεται ο ακέραιος αριθμός Κ, (όπου 0 <= Κ <= 2,000,000) που δηλώνει το πλήθος των κινήσεων που πραγματοποίησε το ρομποτικό όχημα. Στις επόμενες Κ γραμμές περιέχονται Κ χαρακτήρες που μας εμφανίζουν τη διαδρομή που πραγματοποίησε το όχημα. Οι χαρακτήρες αυτοί μπορεί να είναι U, D, R, L (Κεφαλαία Λατινικά).
Δεδομένα Εξόδου
Στο αρχείο εξόδου dimokritos.out θα πρέπει να γράψετε τους αριθμούς των αισθητήρων που έχουν «αντιληφθεί» το ρομποτικό όχημα καθώς και τον αριθμό (πλήθος) ων διεγέρσεων που έχει δεχτεί. Οι αριθμοί των αισθητήρων πρέπει να είναι ταξινομημένοι σε αύξουσα σειρά και κάθε αισθητήρας πρέπει να είναι σε με μια χωριστή γραμμή. Ο αριθμός των διεγέρσεων θα ξεχωρίζει με ένα κενό. Εάν κανένας αισθητήρας δεν «αντιλήφθηκε» το όχημα, στη πρώτη και μόνη γραμμή του αρχείου εξόδου πρέπει να γράψετε "-1". (Κανένας άλλος χαρακτήρας, δεν πρέπει να υπάρχει μετά τον τελευταίο αριθμό κάθε γραμμής).
(Παρατήρηση: Θεωρούμε ότι η παρακολούθηση κάθε μετακινούμενου κιβωτίου ξεκινάει όταν αυτό βρεθεί στην αρχή των αξόνων. Επίσης: Από τη στιγμή που κινηθεί το ρομποτικό όχημα μεταφοράς, ενεργοποιούνται και οι 9 αισθητήρες, γύρω και πάνω από την αρχή των αξόνων (θέση 0,0) όπου και θεωρούμε ότι υπάρχει πάντα αισθητήρας)
Παραδείγματα αρχείων εισόδου - εξόδου
dimokritos1.in
Παράθεση:
15
0 0
-1 0
-1 1
0 1
1 1
1 0
1 -1
0 -1
-1 -1
2 0
2 -1
2 1
-1 2
0 2
1 2
1
R
---------
dimokritos1.outΠαράθεση:
1 2
2 1
3 1
4 2
5 2
6 2
7 2
8 2
9 1
10 1
11 1
12 1
-------------------------------------------------------
-------------------------------------------------------
dimokritos2.inΠαράθεση:
25
-2 -2
-2 -1
-2 0
-2 1
-2 2
-1 2
0 2
1 2
2 2
2 1
2 0
2 -1
2 -2
1 -2
0 -2
-1 -2
-1 0
-1 1
0 1
1 1
1 0
1 -1
0 -1
-1 -1
0 0
0
--------------------
dimokritos2.outΠαράθεση:
-1
-------------------------------------------------------
-------------------------------------------------------
dimokritos3.inΠαράθεση:
17
0 0
-1 0
-1 1
0 1
1 1
1 0
1 -1
0 -1
-1 -1
2 0
2 -1
2 1
-1 2
0 2
1 2
4 0
3 1
3
R
U
R
--------------------
dimokritos3.outΠαράθεση:
1 3
2 1
3 1
4 3
5 4
6 4
7 2
8 2
9 1
10 3
11 1
12 3
14 1
15 2
17 1