Τώρα είναι Πέμ 28 Μαρ 2024 11:41 pm

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




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 2 Δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Δημόκριτος **
ΔημοσίευσηΔημοσιεύτηκε: Τρί 18 Ιαν 2005 04:18 pm 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
Το επόμενο ζήτημα (εξαιρετικά όμορφο :lol: ) αποτελεί ΘΕΜΑ Β' ΦΑΣΗΣ του 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

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


Κορυφή
 Προφίλ  
Απάντηση με παράθεση  
 Θέμα δημοσίευσης:
ΔημοσίευσηΔημοσιεύτηκε: Τρί 08 Μαρ 2005 12:58 pm 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
Α' Τρόπος
Με χρήση διδιαστατου πίνακα (πλέγμα αισθητήρων)

Syntax: [ Download ] [ Hide ]

ΠΡΟΓΡΑΜΜΑ Δημοκριτος
ΣΤΑΘΕΡΕΣ
  s=1401
  num=2000000
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: sensors[s,s],i,j,N,center,x,y,freq[num],temp,centerX,centerY,moves,k,max
  ΧΑΡΑΚΤΗΡΕΣ: route
ΑΡΧΗ

  center <-- s DIV 2 + 1
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ s
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ s
      sensors[i,j] <-- 0
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΔΙΑΒΑΣΕ N
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΔΙΑΒΑΣΕ x,y
    sensors[center-y,center+x] <-- i
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΔΙΑΒΑΣΕ moves

  ΑΝ  moves<>0 ΤΟΤΕ    !============

    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
      freq[i] <-- 0
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    centerX <-- center
    centerY <-- center
    max <-- 0
    ΓΙΑ k ΑΠΟ 0 ΜΕΧΡΙ moves      !------------------------
      ΑΝ k>0 ΤΟΤΕ
        ΔΙΑΒΑΣΕ route
        ΑΝ  route ='U' ΤΟΤΕ
          centerX <-- centerX-1
        ΑΛΛΙΩΣ_ΑΝ route ='D' ΤΟΤΕ
          centerX <-- centerX+1
        ΑΛΛΙΩΣ_ΑΝ route ='R' ΤΟΤΕ
          centerY <-- centerY+1
        ΑΛΛΙΩΣ_ΑΝ route ='L' ΤΟΤΕ
          centerY <-- centerY-1
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ                        

      ΓΙΑ i ΑΠΟ -1 ΜΕΧΡΙ 1
        ΓΙΑ j ΑΠΟ -1 ΜΕΧΡΙ 1
          temp <-- sensors[centerX+i ,centerY+j]
          ΑΝ  temp <>0 ΤΟΤΕ
            freq[temp] <-- freq[temp]+1
          ΤΕΛΟΣ_ΑΝ
          ΑΝ  temp>max ΤΟΤΕ
            max <-- temp
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


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

    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ max
      ΑΝ  freq[i]<>0 ΤΟΤΕ
        ΓΡΑΨΕ i,' ',freq[i]
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΛΛΙΩΣ             !============
    ΓΡΑΨΕ '-1'
  ΤΕΛΟΣ_ΑΝ

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


 

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

Β' Τρόπος
Με χρήση μονοδιάστατων πινάκων

Syntax: [ Download ] [ Hide ]

ΠΡΟΓΡΑΜΜΑ Δημοκριτος_Β
ΣΤΑΘΕΡΕΣ
  num=2000000
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:Xs[num],Ys[num],freq[num],N,moves,sens,k,X,Y,i,j,max
  ΧΑΡΑΚΤΗΡΕΣ: route
ΑΡΧΗ
  ΔΙΑΒΑΣΕ N
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ N
    ΔΙΑΒΑΣΕ Xs[i],Ys[i]
    freq[i] <-- 0
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  X <-- 0
  Y <-- 0
  ΔΙΑΒΑΣΕ moves

  ΑΝ  moves<>0 ΤΟΤΕ    !====

    ΓΙΑ k ΑΠΟ 0 ΜΕΧΡΙ moves !-----------------------------------

      ΑΝ k>0 ΤΟΤΕ
        ΔΙΑΒΑΣΕ route
        ΑΝ route='U' ΤΟΤΕ
          Y <-- Y+1
        ΑΛΛΙΩΣ_ΑΝ  route='D' ΤΟΤΕ
          Y <-- Y-1
        ΑΛΛΙΩΣ_ΑΝ  route='L' ΤΟΤΕ
          X <-- X-1
        ΑΛΛΙΩΣ_ΑΝ  route='R' ΤΟΤΕ
          X <-- X+1
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ

      ΓΙΑ sens ΑΠΟ 1 ΜΕΧΡΙ N
        ΓΙΑ i ΑΠΟ -1 ΜΕΧΡΙ 1
          ΓΙΑ j ΑΠΟ -1 ΜΕΧΡΙ 1
            ΑΝ ( Xs[sens]=X+i) ΚΑΙ (Ys[sens]=Y+j)  ΤΟΤΕ
              freq[sens] <-- freq[sens]+1
            ΤΕΛΟΣ_ΑΝ
          ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
        ΑΝ  sens>max ΤΟΤΕ
          max <-- sens
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

    ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ max
      ΑΝ freq[i]<>0 ΤΟΤΕ
        ΓΡΑΨΕ i,' ',freq[i]
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΛΛΙΩΣ             !====
    ΓΡΑΨΕ '-1'
  ΤΕΛΟΣ_ΑΝ

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


 

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


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

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


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

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


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

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