Τώρα είναι Τρί 19 Μαρ 2024 07:52 am

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




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 
Συγγραφέας Μήνυμα
ΔημοσίευσηΔημοσιεύτηκε: Κυρ 07 Νοέμ 2010 10:30 pm 
Χωρίς σύνδεση

Εγγραφή: Τρί 22 Απρ 2008 11:05 am
Δημοσιεύσεις: 21
Παράθεση:
Το πρόβλημα είναι το εξής
23 ο ς ΠΑΝΕΛΛΗΝΙΟΣ ΔΙΑΓΩΝΙΣΜΟΣ ΠΛΗΡΟΦΟΡΙΚΗΣ
ΘΕΜΑ Α΄ ΦΑΣΗΣ
ΜΕΓΙΣΤΟΠΟΙΗΣΗ ΚΕΡΔΟΥΣ
2 η έκδοση
Οι τιμές κάποιων αγαθών ή τίτλων (π.χ. πετρελαίου, χρυσού,
μετοχών αλλά και βασικών τροφίμων όπως των αλεύρων, της
ζάχαρης κ.λπ.) διαμορφώνονται καθημερινά βάσει της προσφοράς
και της ζήτησης, αλλά και με βάση την εκτίμηση για τη μελλοντική
τους πορεία. Αποτέλεσμα αυτών των συναλλαγών είναι οι τιμές
αυτές να αλλάζουν από μέρα σε μέρα. Κάποιοι εκμεταλλεύονται
αυτήν την αυξομείωση των τιμών, αγοράζοντας μία ποσότητα (ή
δικαίωμα σε ποσότητα) φθηνά, και έπειτα πουλούν την ίδια
ποσότητα ή δικαίωμα ακριβότερα. Το κέρδος εκφράζεται από το λόγο
της τιμής πώλησης προς την τιμή αγοράς. Έστω ότι γνωρίζουμε την
τιμή που έχει κάποιο αγαθό κάθε μέρα για ένα μεγάλο χρονικό
διάστημα. Θέλουμε να υπολογίσουμε το μέγιστο κέρδος που θα
μπορούσε κάποιος να αποκομίσει με μία αγορά και στη συνέχεια μία
πώληση.
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI το
οποίο να διαβάζει το πλήθος των ημερών για τις οποίες είναι γνωστή
η τιμή του αγαθού, την τιμή του αγαθού για κάθε μία από αυτές τις
ημέρες, και να υπολογίζει το μέγιστο δυνατό κέρδος από μία αγορά
και στη συνέχεια μία πώληση.
Αρχεία Εισόδου:
Τα αρχεία εισόδου με όνομα profit.in είναι αρχεία κειμένου με την
εξής δομή: Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό N, το
πλήθος των ημερών για τις οποίες είναι γνωστή η τιμή του αγαθού
(1 ≤ N ≤ 1.000.000). Η δεύτερη γραμμή περιέχει N ακέραιους
αριθμούς Χi (για 1 ≤ i ≤ N), χωρισμένους μεταξύ τους με κενά
διαστήματα, την τιμή του αγαθού κάθε μέρα (1 ≤ Χi ≤ 1.000).
Αρχεία Εξόδου:
Τα αρχεία εξόδου με όνομα profit.out είναι αρχεία κειμένου με την
εξής δομή: Έχουν μία γραμμή με έναν πραγματικό αριθμό P, το
μέγιστο δυνατό κέρδος από μία αγορά και στη συνέχεια μία πώληση,
Σελίδα 1 από 2
Copyright ΕΠΥ 2010-11. Στουρνάρη 37, Αθήνα 106 82 Stournari Str 37 PC 106 82, Athens, Greece
 +30-210-3300999, +30-210-3301893 E-mail: epy@epy.gr, Web: http://www.epy.gr
ΕΛΛΗΝΙΚΗ ΕΤΑΙΡΕΙΑ
ΕΠΙΣΤΗΜΟΝΩΝ ΚΑΙ ΕΠΑΓΓΕΛΜΑΤΙΩΝ
ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΕΠΙΚΟΙΝΩΝΙΩΝ
ΜΕΛΟΣ IFIP, IOI Org.
GREEK COMPUTER SOCIETY
MEMBER OF IFIP, IOI Org.
δηλαδή τη μέγιστη τιμή του λόγου Xi / Xj όταν j ≤ i. Ο αριθμός P
πρέπει να στρογγυλοποιείται με ακρίβεια τριών δεκαδικών ψηφίων.
Παραδείγματα Αρχείων Εισόδου - Εξόδου:
1ο
profit.in profit.out
10
5 4 3 10 11 9 8 8 8 8
3.667
Επεξήγηση παραδείγματος 1: Το μέγιστο κέρδος προκύπτει αν κάποιος
αγοράσει την τρίτη μέρα (Χ3 = 3) και πουλήσει την πέμπτη (Χ5 = 11). Το
κέρδος είναι Χ5 / Χ3 = 11 / 3 = 3.6666666…
2ο
profit.in profit.out
10
9 8 15 5 6 9 8 10 3 5
2.000
Επεξήγηση παραδείγματος 2: Το μέγιστο κέρδος προκύπτει αν κάποιος
αγοράσει την τέταρτη μέρα (Χ4 = 5) και πουλήσει την όγδοη (Χ8 = 10). Το
κέρδος είναι Χ8 / Χ4 = 10 / 5 = 2.
3ο
profit.in profit.out
10
9 8 7 6 5 4 3 2 1 1
1.000
Επεξήγηση παραδείγματος 3: Η τιμή του προϊόντος μειώνεται σταθερά,
κατά συνέπεια δεν είναι δυνατό να προκύψει αληθινό κέρδος. Η μέγιστη
τιμή του λόγου είναι 1, αν κάποιος αγοράσει και πουλήσει την ίδια μέρα.
Μέγιστος χρόνος: 1 sec
Σελίδα 2 από 2
Copyright ΕΠΥ

Παράθεση:
Παρακάτω ο κώδικας που ανέπτυξα που μπορεί να αντιγραφεί σχεδον πιστά και στην pascal μια απο τις γλώσσες του ΙΟΙ.Για εξηγήσεις στον κώδικα μην δηστάσετε :mrgreen:

Κώδικας:
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: ι,πιν[1000001],θ,οριο_τελ,μαχ,μιν
  ΠΡΑΓΜΑΤΙΚΕΣ:μαχ_π
  ΛΟΓΙΚΕΣ: αλλ
ΑΡΧΗ

  ΔΙΑΒΑΣΕ πιν[1] !Αριθμός εγγραφών
  ΓΙΑ ι από 2 μέχρι πιν[1]+1
    ΔΙΑΒΑΣΕ πιν[ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!!!!Ολο το παραπάνω αντικαθήστατε με ανάγνωση από το αρχείο.

  για ι από 3 μέχρι πιν[1]+1
    αν πιν[ι]>=μαχ τότε
      μαχ <-- πιν[ι]
      θ <-- ι
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  μιν <-- μαχ

  ΓΙΑ ι από 2 μέχρι θ
    αν πιν[ι]<=μιν τότε
      μιν <-- πιν[ι]
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  μαχ_π <-- μαχ/μιν

  αν θ+1<πιν[1] τότε
    αλλ <-- ΑΛΗΘΗΣ
    οριο_τελ <-- θ+1
    ΟΣΟ οριο_τελ<=πιν[1] και αλλ= ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
      αλλ <-- ΨΕΥΔΗΣ
      για ι από οριο_τελ μέχρι πιν[1]+1
        αν πιν[ι]<μιν τότε
          αλλ <-- ΑΛΗΘΗΣ
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

      αν αλλ= ΑΛΗΘΗΣ τότε
        μαχ <-- 0                                 
        για ι από οριο_τελ+1 μέχρι πιν[1]+1
          αν πιν[ι]>=μαχ τότε
            μαχ <-- πιν[ι]
            θ <-- ι
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

        μιν <-- μαχ

        ΓΙΑ ι από οριο_τελ μέχρι θ
          αν πιν[ι]<=μιν τότε
            μιν <-- πιν[ι]
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

        αν (μαχ/μιν)>μαχ_π τότε
          μαχ_π <-- μαχ/μιν
        ΤΕΛΟΣ_ΑΝ
        οριο_τελ <-- θ+1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΑΝ

  ΓΡΑΨΕ 'Μεγιστο δυνατο κέρδος:',μαχ_π:4:3
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Παράθεση:
Είδατε πως δεν χειρήστικα αρχεία...Ετσι και αλλιώς είναι ανούσιο. :wink:


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

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


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

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


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

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