Τώρα είναι Τετ 06 Νοέμ 2024 10:31 am

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Χρωματική Σήμανση Τρένων ***
ΔημοσίευσηΔημοσιεύτηκε: Δευτ 17 Ιαν 2005 12:15 am 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
ΧΡΩΜΑΤΙΚΗ ΣΗΜΑΝΣΗ ΤΡΕΝΩΝ
ΠΡΟΒΛΗΜΑ 2ης ΦΑΣΗΣ
16ου ΠΑΝΕΛΛΗΝΙΟΥ ΔΙΑΓΩΝΙΣΜΟΥ ΠΛΗΡΟΦΟΡΙΚΗΣ ( Φεβρουάριος 2004)

Το Ευρωπαϊκό σιδηροδρομικό δίκτυο εξυπηρετεί καθημερινά εκατοντάδες χιλιάδες πολίτες. Το δίκτυο αυτό, συνδέει όλες τις μεγάλες πόλεις της Ευρώπης. Το δίκτυο σχηματικά, αποτελείται από σταθμούς, έναν σε κάθε μεγάλη πόλη και τις γραμμές που τους συνδέουν.

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

Σε μια προσπάθεια να διευκολυνθεί το επιβατικό κοινό, οι αρμόδιοι φορείς των Σιδηροδρόμων αποφάσισαν να χρωματίσουν τα τρένα, ώστε όλα τα τρένα που εκτελούν την ίδια διαδρομή να έχουν το ίδιο χρώμα. Για να μην μπερδευτεί το κοινό, αποφασίστηκε, ότι τα τρένα που εκτελούν διαφορετική διαδρομή αλλά περνούν από τον ίδιο σταθμό θα πρέπει να έχουν διαφορετικό χρώμα. Εξαιτίας περιορισμών, για το έργο αυτό πρέπει να χρησιμοποιηθούν όσο το δυνατόν λιγότερα διαφορετικά χρώματα.

Γράψτε ένα πρόγραμμα για να βοηθήσετε να χρωματιστούν τα τρένα χρησιμοποιώντας τον ελάχιστο δυνατό διαφορετικό αριθμό χρωμάτων.

Δεδομένα εισόδου
Στην πρώτη γραμμή δίνονται δύο ακέραιοι, Ν και Μ, χωριζόμενοι με ένα κενό, που αντιστοιχούν στο πλήθος των σταθμών και στο πλήθος των διαδρομών. Είναι 1 <= Ν <= 100, 1 <= Μ <= 2000. Ο κάθε σταθμός έχει έναν μοναδικό κωδικό αριθμό, από το 1 εώς το Ν.
Η κάθε μία από τις Μ γραμμές που ακολουθούν περιγράφουν την κάθε διαδρομή.
Η περιγραφή κάθε διαδρομής ξεκινάει με έναν ακέραιο Ρ. Ο αριθμός Ρ είναι ο αριθμός των σταθμών από τους οποίους περνάνε τα τρένα που πραγματοποιούν τη διαδρομή, συμπεριλαμβανομένων και των σταθμών αφετηρίας και τερματισμού. Να θεωρήσετε ότι οι σταθμοί αφετηρίας και τερματισμού είναι πάντα διαφορετικοί μεταξύ τους. Ακολουθούν Ρ ακέραιοι, που αντιστοιχούν στον κωδικό αριθμό των σταθμών αυτών. Όλοι οι αριθμοί στη γραμμή εισόδου χωρίζονται μεταξύ τους με ένα κενό χαρακτήρα.

Δεδομένα εξόδου
Στην πρώτη γραμμή του αρχείου εξόδου θα πρέπει να γράψετε τον ελάχιστο αριθμό των χρωμάτων που απαιτούνται για το χρωματισμό των διαδρομών, ώστε να πληρούνται οι προδιαγραφές χρωματισμού.
Στη δεύτερη γραμμή του αρχείου εξόδου θα πρέπει να γράψετε Μ ακέραιους αριθμούς, χωριζόμενους με ένα κενό χαρακτήρα. Οι αριθμοί αυτοί θα πρέπει να αναπαριστούν έναν από τους δυνατούς τρόπους χρωματισμού τον τρένων κάθε διαδρομής. Ο πρώτος αριθμός θα αντιστοιχεί στο χρώμα της πρώτης διαδρομής, ο δεύτερος στο χρώμα της δεύτερης κ.ο.κ.

Παραδείγματα
[ Ν=6 (πλήθος διαφορετικών σταμών), Μ=3 (πλήθος διαφορετικών γραμμών) ]
1η γραμμή: το τραίνο περνάει από 3 σταθμούς: 1 2 3
2η γραμμή: το τραίνο περνάει από 3 σταθμούς: 4 5 6
3η γραμμή: το τραίνο περνάει από 4 σταθμούς: 1 2 5 6

Input1.txt
Παράθεση:
6 3
3 1 2 3
3 4 5 6
4 1 2 5 6


Απαιτούνται 2 χρώματα
1η γραμμή: χρώμα 1
2η γραμμή: χρώμα 1
3η γραμμή: χρώμα 2

Output1.txt
Παράθεση:
2
1 1 2


---------------------------------------------------
Input2.txt
Παράθεση:
6 4
6 1 2 3 4 5 6
3 2 3 4
2 5 4
2 5 6

Output2.txt
Παράθεση:
3
1 2 3 2

---------------------------------------------------

Input3.txt
Παράθεση:
8 4
3 3 2 1
3 2 5 6
4 4 5 6 7
2 8 4


Output3.txt
Παράθεση:
2
1 2 1 2

---------------------------------------------------------

Σημείωση: Τα δεδομένα εισόδου που θα δίνονται στο πρόγραμμα θα είναι πάντα έγκυρα, όπως περιγράφονται από το πρόβλημα. Έλεγχος εγκυρότητας δεν θα απαιτείται.

-------------------**************-----------------------------

Να με συγχωρήσετε για την παράθεση της εκφώνησης έξω από τα πεδία του κώδικα, αλλά το μέγεθος της με έκανε να την καταχωρήσω με την παραπάνω μορφή :(

Ένα πράγματι εξαιρετικά όμορφο πρόβλημμα (και μάλον λίγο δυσκολούτσικο :shock: ), που αναδεικνύει τις δυναμικές δομές (αν Ν και Μ πολύ μεγάλα)...... Στα πλαίσια όμως της ΑΕΠΠ ας περιοριστούμε να προτείνουμε μια λύση με χρήση στατικών πινάκων. :wink:

Syntax: [ Download ] [ Hide ]

ΠΡΟΓΡΑΜΜΑ trains
ΣΤΑΘΕΡΕΣ
  stations=200
  routes=100
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:i,j,D[routes],data[routes,stations],line,max,temp[routes,stations]
  ΑΚΕΡΑΙΕΣ:stn,rts,c,row,coloumn,r,lim[routes],colour[routes]
  ΛΟΓΙΚΕΣ: ομοιο,καταχωρηση
ΑΡΧΗ

  ΔΙΑΒΑΣΕ stn,rts
  !---------------------------------------------------

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ rts
    ΔΙΑΒΑΣΕ D[i]
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ D[i]
      ΔΙΑΒΑΣΕ data[i,j]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ rts
    lim[i] <-- 0
    temp[i,1] <-- 0
    colour[i] <-- 0
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  !---------------------------------------------------
  line <-- 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ rts

    καταχωρηση <-- ψευδής
    line <-- line+1
    row <-- 1

    ΟΣΟ (row<=routes) ΚΑΙ ΟΧΙ καταχωρηση ΕΠΑΝΑΛΑΒΕ
      ομοιο <-- ψευδής

      ΓΙΑ coloumn ΑΠΟ 1 ΜΕΧΡΙ lim[row]
        j <-- 1
        ΟΣΟ (j<=D[line]) ΚΑΙ ΟΧΙ ομοιο ΕΠΑΝΑΛΑΒΕ
          ΑΝ temp[row,coloumn]=data[line,j] ΤΟΤΕ
            ομοιο <-- αληθής
          ΤΕΛΟΣ_ΑΝ
          j <-- j+1
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

      ΑΝ ομοιο ΤΟΤΕ
        row <-- row+1
      ΑΛΛΙΩΣ
        καταχωρηση <-- αληθής
      ΤΕΛΟΣ_ΑΝ

    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    c <-- 1
    ΓΙΑ j ΑΠΟ lim[row]+1 ΜΕΧΡΙ lim[row]+D[line]
      temp[row,j] <-- data[line,c]
      c <-- c+1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    lim[row] <-- lim[row]+D[line]
    colour[i] <-- row
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  !---------------------------------------------------

  max <-- colour[1]
  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ rts
    ΑΝ colour[i]>max ΤΟΤΕ
      max <-- colour[i]
    ΤΕΛΟΣ_ΑΝ                                                
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Μέγιστος αριθμός χρωμάτων=',max

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ rts
    ΓΡΑΨΕ_ colour[i],' '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ


 

_________________
Φρειδερίκος Κώστας
FreiderikosK@hotmail.com


Κορυφή
 Προφίλ  
Απάντηση με παράθεση  
Τελευταίες δημοσιεύσεις:  Ταξινόμηση ανά  
Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επισυνάπτετε αρχεία σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Προβολές: