Το Στέκι των Πληροφορικών

Γενικά => Γενικά Παιδαγωγικά, Επιστημονικά και Τεχνικά Θέματα => Διαγωνισμοί => Μήνυμα ξεκίνησε από: skananitos στις 23 Οκτ 2011, 01:01:46 μμ

Τίτλος: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: skananitos στις 23 Οκτ 2011, 01:01:46 μμ
Οι εγγραφές ξεκίνησαν! Περισσότερες πληροφορίες εδώ: http://www.pdp.gr/default.asp?pid=1&la=1
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Vangelis στις 23 Οκτ 2011, 07:45:12 μμ
Θα πρέπει να σημειωθεί ότι ψυχή του Πανελλήνιου Διαγωνισμού Πληροφορικής είναι ένας συνάδελφός μας ο Μανώλης Μόρμορης που διδάσκει στο 2ο Λύκειο Βριλησσίων ο οποίος διαθέτει άπειρο χρόνο σε αυτή την δραστηριότητα χωρίς κανένα οικονομικό όφελος.

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


Ο Πανελλήνιος Διαγωνισμός Πληροφορικής προβάλει και δίνει κύρος στον κλάδο μας και θεωρώ ότι πρέπει όλοι να τον προωθήσουμε.  Αν λοιπόν έχετε μαθητές με ιδιαίτερες ανησυχίες στον προγραμματισμό καλό είναι να τους ενημερώσετε και να ενθαρρύνετε την συμμετοχή τους .
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 17 Δεκ 2011, 03:08:53 μμ
Λείπει κάτι από το Θέμα της Α' Φάσης ;

http://www.pdp.gr/files/24a/PDP_24_A.pdf
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 17 Ιαν 2012, 09:39:59 μμ
(http://upload.wikimedia.org/wikipedia/commons/6/63/Animation_Sieb_des_Eratosthenes.gif)
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: sstergou στις 18 Ιαν 2012, 08:41:51 πμ
Πάντα μου άρεσε αυτός ο αλγόριθμος!! Είναι από τη δεύτερη φάση;
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 18 Ιαν 2012, 12:44:24 μμ
Εμμ, χμμ... την εικόνα την ανέβασα ενδεικτικά! Δες το θέμα από τον πιο πάνω σύνδεσμο!
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: evry στις 19 Ιαν 2012, 12:12:32 πμ
Πράγματι πολύ ενδιαφέρον αλγόριθμος , αρκεί φυσικά να τον ξέρεις γιατί να τον επινοήσεις μόνος σου λίγο δύσκολο μου φαίνεται.
Είναι προφανές ότι το συγκεκριμένο θέμα δεν απευθύνεται σε σκεπτόμενους μαθητές αλλά σε μαθητές που είναι καλά "διαβασμένοι" και προετοιμασμένοι για τέτοιους διαγωνισμούς ή έχουν την κατάλληλη καθοδήγηση.
Επίσης θα ήθελα πάρα πολύ κάποιος αν μπορεί με βάση την εκφώνηση να μου αποδείξει γιατί η απάντηση στο θέμα που δίνεται είναι αυτό που προτείνει ο Νίκος. (το λέω έτσι γιατί δεν θέλω να πω ευθέως την "απάντηση")
Προφανώς αυτή την απάντηση θέλουν, αλλά από που προκύπτει αυτό?
Δηλαδή αν εγώ φτιάξω έναν αλγόριθμο ο οποίος τρέχει μόνο με τα testcases που δίνονται κανονικά δεν θα πρέπει να θεωρηθεί σωστός?

ΥΓ. Ας με συγχωρήσουν όσοι δεν κατάλαβαν τι εννοώ αλλά προσπαθώ να θίξω το θέμα χωρίς να πω την απάντηση
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 19 Ιαν 2012, 09:09:39 πμ
... από που προκύπτει αυτό?

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

Λείπει κάτι από το Θέμα της Α' Φάσης ;

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

(Αλήθεια, πού είναι το 2; )
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: 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.
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: dski στις 01 Φεβ 2012, 05:11:44 μμ
  Υπάρχει  κάποιο παράδειγμα διαθέσιμο? Για να πω την αμαρτία μου, δεν ξέρω αν φταίει η μεσημεριανή μου κούραση αλλά δε μπορώ να καταλάβω τι ακριβώς ζητάει η άσκηση. Δηλ. ο Μίλτος αγοράζει Μ φρούτα και μετά διαλέγει τυχαία κάποια (από 1 ως Μ φρούτα) από αυτά. Αν Σ είναι όλες οι πιθανές επιλογές (συνδυασμοί) από τα Μ φρούτα θα πρέπει 1/Σ = 1/Ρ (αφού μόνο ένας συνδυασμός υπάρχει όπου ο Μίλτος επιλέγει όλα τα φρούτα του).Αν υπάρχει Μ που παράγει τέτοιο Σ ώστε 1/Κ=1/Ρ τότε θα πρέπει να επιλεγούν τα Μ φτηνότερα φρούτα ώστε το κόστος να είναι το ελάχιστο.Το καταλαβαίνω καλά ή νυστάζω πολύ;
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: gpapargi στις 02 Φεβ 2012, 11:52:50 πμ
Αν καταλαβαίνω καλά (γιατί δεν είμαι σίγουρος) σημαίνει το εξής: (δίνω παράδειγμα)

Ας πούμε ότι διαλέγω 10 φρούτα. Στη συνέχεια από αυτά τα 10 διαλέγω κάποια. Μπορεί να διαλέξω 1, μπορεί 2, μπορεί 3 κλπ. Το κάθε ένα από αυτά τα νούμερα (πχ το 3) μπορεί να γίνει με ένα πλήθος από τρόπους (το 10 ανά 3 που λέμε). Θα πρέπει να προστεθούν όλοι οι τρόποι με τους οποίους διαλέγω 1, 2, 3… 10 (εξαιρείται το 0 γιατί λέει ότι επιλέγεται τουλάχιστο 1) και έτσι έχω όλους τους δυνατούς τρόπους με τους οποίους μπορούν να διαλέξουν στην τύχη φρούτα (10 ανά 1 και 10 ανά 2 κλπ). Ένας από αυτούς είναι και το να τα πάρει όλα, οπότε αν υποθέσουμε μια ομοιόμορφη κατανομή στην επιλογή υποσυνόλου, έχω κάποια πιθανότητα να επιλεγούν και όλα. Θα πρέπει το πλήθος των επιλεγμένων (εδώ το 10) να είναι τέτοιο ώστε η πιθανότητα να επιλεγούν όλα (εδώ και τα 10) να είναι η ζητούμενη. 
Αυτό κατάλαβα ότι  εννοεί με τη φράση «Αν επιλέξει τυχαία μερικά από αυτά (τουλάχιστον ένα), η πιθανότητα να τα έχει επιλέξει όλα να είναι ακριβώς 1/P, όπου P θετικός ακέραιος»
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: evry στις 02 Φεβ 2012, 11:49:25 μμ
Πλάκα πλάκα μια και μιλάμε για διαγωνισμούς, μου ήρθε στο μυαλό μια κατηγορία αλγορίθμων του κλάδου της αλγοριθμικής που λέγεται "Υπολογιστική Γεωμετρία". Το συγκεκριμένο μάθημα διδάσκεται σε ελάχιστα τμήματα πληροφορικής.
Ένα ενδιαφέρον πρόβλημα που εμπίπτει σε αυτή την κατηγορία είναι η εύρεση του λεγόμενου convex hull ενός συνόλου σημείων το οποίο έχει αρκετό ενδιαφέρον
Παραθέτω κάποιους συνδέσμους
http://en.wikipedia.org/wiki/Convex_hull (http://en.wikipedia.org/wiki/Convex_hull)

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

Παραθέτω και κάποια ακόμα επεξηγηματικά tutorials για όποιον ενδιαφέρεται στα οποία υπάρχει και οπτικοποίηση του αλγορίθμου
http://people.csail.mit.edu/thies/6.046-web/graham.pdf (http://people.csail.mit.edu/thies/6.046-web/graham.pdf)
http://www.cs.princeton.edu/courses/archive/fall11/cos226/demo/99DemoGrahamScan.pdf (http://www.cs.princeton.edu/courses/archive/fall11/cos226/demo/99DemoGrahamScan.pdf)
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 23 Φεβ 2012, 11:05:24 πμ
Από την Β φάση του διαγωνισμού (http://www.pdp.gr/default.asp?pid=6&la=1&fid=2)

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI το οποίο θα δέχεται ως είσοδο Ν ακέραιους αριθμούς (θετικούς και αρνητικούς) σε αύξουσα σειρά. Το πρόγραμμα θα βρίσκει τους δύο αριθμούς που το άθροισμά τους είναι πιο κοντά στο 0 ώστε να “οδηγήσει” τα αντίστοιχα κανάλια στον κατάλληλο τελεστικό ενισχυτή.
Τίτλος: Απ: 24ος Πανελλήνιος Μαθητικός Διαγωνισμός Πληροφορικής
Αποστολή από: infinity στις 07 Σεπ 2012, 11:48:13 μμ
Τι λέτε για την παρακάτω άσκηση?
είναι από το 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 αν θυμάμαι καλά.Όταν το είχα λύσει καθόμουν κανένα μισάωρο  για να καταλάβω τι ακριβώς ζητάει.Είναι κακοδιατυπωμένο πρόβλημα, αλλά όχι δύσκολο