Γενικά > Διαγωνισμοί

24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής

<< < (3/3)

gpapargi:
Αν καταλαβαίνω καλά (γιατί δεν είμαι σίγουρος) σημαίνει το εξής: (δίνω παράδειγμα)

Ας πούμε ότι διαλέγω 10 φρούτα. Στη συνέχεια από αυτά τα 10 διαλέγω κάποια. Μπορεί να διαλέξω 1, μπορεί 2, μπορεί 3 κλπ. Το κάθε ένα από αυτά τα νούμερα (πχ το 3) μπορεί να γίνει με ένα πλήθος από τρόπους (το 10 ανά 3 που λέμε). Θα πρέπει να προστεθούν όλοι οι τρόποι με τους οποίους διαλέγω 1, 2, 3… 10 (εξαιρείται το 0 γιατί λέει ότι επιλέγεται τουλάχιστο 1) και έτσι έχω όλους τους δυνατούς τρόπους με τους οποίους μπορούν να διαλέξουν στην τύχη φρούτα (10 ανά 1 και 10 ανά 2 κλπ). Ένας από αυτούς είναι και το να τα πάρει όλα, οπότε αν υποθέσουμε μια ομοιόμορφη κατανομή στην επιλογή υποσυνόλου, έχω κάποια πιθανότητα να επιλεγούν και όλα. Θα πρέπει το πλήθος των επιλεγμένων (εδώ το 10) να είναι τέτοιο ώστε η πιθανότητα να επιλεγούν όλα (εδώ και τα 10) να είναι η ζητούμενη. 
Αυτό κατάλαβα ότι  εννοεί με τη φράση «Αν επιλέξει τυχαία μερικά από αυτά (τουλάχιστον ένα), η πιθανότητα να τα έχει επιλέξει όλα να είναι ακριβώς 1/P, όπου P θετικός ακέραιος»

evry:
Πλάκα πλάκα μια και μιλάμε για διαγωνισμούς, μου ήρθε στο μυαλό μια κατηγορία αλγορίθμων του κλάδου της αλγοριθμικής που λέγεται "Υπολογιστική Γεωμετρία". Το συγκεκριμένο μάθημα διδάσκεται σε ελάχιστα τμήματα πληροφορικής.
Ένα ενδιαφέρον πρόβλημα που εμπίπτει σε αυτή την κατηγορία είναι η εύρεση του λεγόμενου convex hull ενός συνόλου σημείων το οποίο έχει αρκετό ενδιαφέρον
Παραθέτω κάποιους συνδέσμους
http://en.wikipedia.org/wiki/Convex_hull

Ένας γρήγορος αλγόριθμος για την εύρεση του περιβλήματος τάξης nlogn είναι ο Graham scan
http://en.wikipedia.org/wiki/Graham_scan
Πρόκειται μάλιστα για έναν αλγόριθμο τόσο απλό που θα μπορούσε κάποιος να τον κάνει ακόμα και στο σχολείο!!!

Παραθέτω και κάποια ακόμα επεξηγηματικά tutorials για όποιον ενδιαφέρεται στα οποία υπάρχει και οπτικοποίηση του αλγορίθμου
http://people.csail.mit.edu/thies/6.046-web/graham.pdf
http://www.cs.princeton.edu/courses/archive/fall11/cos226/demo/99DemoGrahamScan.pdf

Νίκος Αδαμόπουλος:
Από την Β φάση του διαγωνισμού

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI το οποίο θα δέχεται ως είσοδο Ν ακέραιους αριθμούς (θετικούς και αρνητικούς) σε αύξουσα σειρά. Το πρόγραμμα θα βρίσκει τους δύο αριθμούς που το άθροισμά τους είναι πιο κοντά στο 0 ώστε να “οδηγήσει” τα αντίστοιχα κανάλια στον κατάλληλο τελεστικό ενισχυτή.

infinity:

--- Παράθεση από: evry στις 31 Ιαν 2012, 08:13:09 μμ ---Τι λέτε για την παρακάτω άσκηση?
είναι από το hellenico, από το διαγωνισμό Ιανουαρίου

Εκφώνηση

Ο Μίλτος το δελφίνι αποφάσισε με τη νέα χρονιά να προσέξει τη διατροφή του, να σταματήσει το fast food και να αρχίσει να τρώει μόνο φρούτα, για να είναι σε φόρμα για τους αγώνες στίβου που γίνονται Βυθό. Έτσι, επισκέφθηκε το super market της γειτονιάς του για να αγοράσει πάρα πολλά φρούτα. Μόλις έφτασε εκεί διαπίστωσε ότι υπάρχουν Ν διαφορετικά είδη φρούτων, όπου το i-οστό από αυτά κοστίζει c κοχύλια το κάθε φρούτο και είναι διαθέσιμες συνολικά b μονάδες φρούτων. Ο Μίλτος ετοιμάζεται να τα αγοράσει όλα, όμως ο υπάλληλος τον σταματάει, περιγράφοντάς του την περίεργη πολιτική του μαγαζιού όσον αφορά τις αγορές φρούτων. Θα πρέπει για τα φρούτα που θα αγοράσει να ισχύει το εξής: Αν επιλέξει τυχαία μερικά από αυτά (τουλάχιστον ένα), η πιθανότητα να τα έχει επιλέξει όλα να είναι ακριβώς 1/P, όπου P θετικός ακέραιος. Να βρείτε το ελάχιστο ποσό χρημάτων που απαιτούνται για να αγοράσει ο Μίλτος κάποια φρούτα σύμφωνα με τους περιορισμούς.
Δεδομένα εισόδου (αρχείο "fruit.in")

Στην πρώτη γραμμή δίνονται οι N,P. Σε κάθε μία από τις επόμενες N γραμμές δίνεται η ποσότητα και το κόστος κάποιου από τα Ν είδη φρούτων.
Δεδομένα εξόδου (αρχείο "fruit.out")

Το ελάχιστο κόστος, ή -1 αν δεν γίνεται να αγοράσει τίποτα.
Περιορισμοί

1<=N<=10000
1<=P<=70000
1<=b,c<=70000

    Όριο χρόνου εκτέλεσης: 5 sec.
    Όριο μνήμης: 64 MB.

--- Τέλος παράθεσης ---

δεν είναι πολύ δύσκολο πρόβλημα, απ' όσο θυμάμαι.. θα πρέπει να είναι dp αν θυμάμαι καλά.Όταν το είχα λύσει καθόμουν κανένα μισάωρο  για να καταλάβω τι ακριβώς ζητάει.Είναι κακοδιατυπωμένο πρόβλημα, αλλά όχι δύσκολο

Πλοήγηση

[0] Λίστα μηνυμάτων

[*] Προηγούμενη σελίδα

Μετάβαση στην πλήρη έκδοση