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

Ξεκίνησε από skananitos, 23 Οκτ 2011, 01:01:46 ΜΜ

« προηγούμενο - επόμενο »

skananitos

Music is life...Live a fun one...Listen to SKA !!! ;-)

Vangelis

Θα πρέπει να σημειωθεί ότι ψυχή του Πανελλήνιου Διαγωνισμού Πληροφορικής είναι ένας συνάδελφός μας ο Μανώλης Μόρμορης που διδάσκει στο 2ο Λύκειο Βριλησσίων ο οποίος διαθέτει άπειρο χρόνο σε αυτή την δραστηριότητα χωρίς κανένα οικονομικό όφελος.


(Κάποτε θα πρέπει να προβάλουμε και ονομαστικά και τα θετικά παραδείγματα)


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

Νίκος Αδαμόπουλος


Νίκος Αδαμόπουλος


sstergou

Πάντα μου άρεσε αυτός ο αλγόριθμος!! Είναι από τη δεύτερη φάση;

Νίκος Αδαμόπουλος

Εμμ, χμμ... την εικόνα την ανέβασα ενδεικτικά! Δες το θέμα από τον πιο πάνω σύνδεσμο!

evry

Πράγματι πολύ ενδιαφέρον αλγόριθμος , αρκεί φυσικά να τον ξέρεις γιατί να τον επινοήσεις μόνος σου λίγο δύσκολο μου φαίνεται.
Είναι προφανές ότι το συγκεκριμένο θέμα δεν απευθύνεται σε σκεπτόμενους μαθητές αλλά σε μαθητές που είναι καλά "διαβασμένοι" και προετοιμασμένοι για τέτοιους διαγωνισμούς ή έχουν την κατάλληλη καθοδήγηση.
Επίσης θα ήθελα πάρα πολύ κάποιος αν μπορεί με βάση την εκφώνηση να μου αποδείξει γιατί η απάντηση στο θέμα που δίνεται είναι αυτό που προτείνει ο Νίκος. (το λέω έτσι γιατί δεν θέλω να πω ευθέως την "απάντηση")
Προφανώς αυτή την απάντηση θέλουν, αλλά από που προκύπτει αυτό?
Δηλαδή αν εγώ φτιάξω έναν αλγόριθμο ο οποίος τρέχει μόνο με τα testcases που δίνονται κανονικά δεν θα πρέπει να θεωρηθεί σωστός?

ΥΓ. Ας με συγχωρήσουν όσοι δεν κατάλαβαν τι εννοώ αλλά προσπαθώ να θίξω το θέμα χωρίς να πω την απάντηση
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Νίκος Αδαμόπουλος

Παράθεση από: evry στις 19 Ιαν 2012, 12:12:32 ΠΜ
... από που προκύπτει αυτό?

Αυτός ήταν από την αρχή ο προβληματισμός μου!

Παράθεση από: Νίκος Αδαμόπουλος στις 17 Δεκ 2011, 03:08:53 ΜΜ
Λείπει κάτι από το Θέμα της Α' Φάσης ;

Θα μπορούσε να είναι απλώς ένας πίνακας που να έχουν εκχωρηθεί οι εικαζόμενοι αριθμοί!

(Αλήθεια, πού είναι το 2; )

evry

Τι λέτε για την παρακάτω άσκηση?
είναι από το 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.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

dski

  Υπάρχει  κάποιο παράδειγμα διαθέσιμο? Για να πω την αμαρτία μου, δεν ξέρω αν φταίει η μεσημεριανή μου κούραση αλλά δε μπορώ να καταλάβω τι ακριβώς ζητάει η άσκηση. Δηλ. ο Μίλτος αγοράζει Μ φρούτα και μετά διαλέγει τυχαία κάποια (από 1 ως Μ φρούτα) από αυτά. Αν Σ είναι όλες οι πιθανές επιλογές (συνδυασμοί) από τα Μ φρούτα θα πρέπει 1/Σ = 1/Ρ (αφού μόνο ένας συνδυασμός υπάρχει όπου ο Μίλτος επιλέγει όλα τα φρούτα του).Αν υπάρχει Μ που παράγει τέτοιο Σ ώστε 1/Κ=1/Ρ τότε θα πρέπει να επιλεγούν τα Μ φτηνότερα φρούτα ώστε το κόστος να είναι το ελάχιστο.Το καταλαβαίνω καλά ή νυστάζω πολύ;

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

#11
Πλάκα πλάκα μια και μιλάμε για διαγωνισμούς, μου ήρθε στο μυαλό μια κατηγορία αλγορίθμων του κλάδου της αλγοριθμικής που λέγεται "Υπολογιστική Γεωμετρία". Το συγκεκριμένο μάθημα διδάσκεται σε ελάχιστα τμήματα πληροφορικής.
Ένα ενδιαφέρον πρόβλημα που εμπίπτει σε αυτή την κατηγορία είναι η εύρεση του λεγόμενου 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
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Νίκος Αδαμόπουλος

Από την Β φάση του διαγωνισμού

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της 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 αν θυμάμαι καλά.Όταν το είχα λύσει καθόμουν κανένα μισάωρο  για να καταλάβω τι ακριβώς ζητάει.Είναι κακοδιατυπωμένο πρόβλημα, αλλά όχι δύσκολο
Dr. Jekyl, Mr. Hyde...