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

20ος ΠΔΠ Γ' Φάση
Ancient Code (code)

[ Μονάδες]

Σε poster που ανάρτησαν δύο υποψήφιοι διδάκτορες αρχαιολογίας κατά τη διάρκεια του 12ου Πανελλήνιου Συνεδρίου Πληροφορικής (ΕΠΥ, Σάμος 2008) παρουσίασαν παλίμψηστο κώδικα της Ελληνιστικής περιόδου, που περιέγραφε τη λειτουργία του Μηχανισμού των Αντικυθήρων. Οι συνάδελφοι της Επιστημονικής Επιτροπής, προκειμένου να επιβεβαιώσουν το σημαντικό αυτό εύρημα, απευθύνθηκαν σε κορυφαίους επιστήμονες των θεωρητικών επιστημών. Βούληση της Επιστημονικής Επιτροπής ήταν το κείμενο να περάσει διαδοχικά από όλους τους ειδικούς με σκοπό να υπάρξει η εγκυρότερη γνώμη. Δυστυχώς όμως οι σχέσεις μεταξύ τους, δεν ήταν οι καλλίτερες δυνατές. Το κείμενο λοιπόν έπρεπε να μεταφερθεί από ειδικό σε ειδικό χωρίς αυτό να μπορεί να γίνει με οποιονδήποτε συνδυασμό. Ο τελευταίος πχ. που θα μελετήσει τον κώδικα, θα πρέπει να διατηρεί επικοινωνία με τον πρώτο, ώστε να μπορεί να το επιστρέψει εκεί από όπου ξεκίνησε.

Πρόβλημα

Να αναπτύξετε πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο: αφού διαβάζει τις συσχετίσεις μεταξύ των επιστημόνων, θα καθορίζει μια τουλάχιστον δυνατή σειρά μεταβίβασης. Αν αυτό δεν μπορεί να συμβεί θα επιστρέφει την τιμή 0. Το κείμενο πρέπει να γυρίσει στον αρχικό παραλήπτη. (Είναι φανερό ότι μπορεί να υπάρχουν περισσότερες από μία λύσεις, οποιαδήποτε σωστή είναι απολύτως αποδεκτή).

Σημείωση 1: Κάθε επιστήμονας έχει τουλάχιστον έναν συνάδελφο με τον οποίο έχει καλές σχέσεις. Η σχέση αυτή είναι αμφίδρομη.

Σημείωση 2: Ο κώδικας δεν μπορεί να μελετηθεί (περάσει) περισσότερες από μία φορές από τον ίδιο επιστήμονα.

Αρχεία εισόδου

Τα αρχεία εισόδου με όνομα code.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή υπάρχει ένας ακέραιος \(N\) (\(10 \leq N \leq 10.000\)), ο αριθμός των συσχετίσεων μεταξύ των επιστημόνων. Οι επόμενες \(N\) γραμμές έχουν την παρακάτω δομή. Ο πρώτος αριθμός \(M\) (\(1 \leq M \leq 1.000\)) κάθε γραμμής, είναι ο αύξων αριθμός ενός επιστήμονα. Ο δεύτερος αριθμός \(K\) (\(1 \leq K \leq 1.000\)) είναι επίσης ο αύξων αριθμός ενός επιστήμονα, με τον οποίο διατηρεί καλές σχέσεις. Η σχέση αυτή είναι αμφίδρομη. (Οι δύο αριθμοί χωρίζονται με ένα κενό).

Αρχεία εξόδου

Τα αρχεία εξόδου με όνομα code.out είναι αρχεία κειμένου με την εξής δομή. Έχουν ακριβώς \(\Pi\) γραμμές (\(10 \leq \Pi \leq 1.000\)), όπου \(\Pi\) ο αριθμός των επιστημόνων. (Άρα ο κώδικας θα περάσει μόνο μια φορά από κάθε επιστήμονα). Στην πρώτη γραμμή είναι ο αριθμός του επιστήμονα στον οποίο θα παραδοθεί πρώτα το κείμενο. Στην τελευταία γραμμή είναι ο αριθμός του τελευταίου επιστήμονα από τον οποίο θα περάσει το κείμενο πριν επιστρέψει στον πρώτο.

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

1o (δύο ισοδύναμα αρχεία εξόδου)

code.in code.out
11
1 2
1 3
1 10
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1
2
3
4
5
6
7
8
9
10

(Η έξοδος είναι ενδεικτική και ΔΕΝ είναι η μόνη σωστή)

Περιορισμοί

  • Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα newline χαρακτήρα.
  • Μέγιστος χρόνος εκτέλεσης: 20 sec.