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

[skananitos]

Οι εγγραφές ξεκίνησαν! Περισσότερες πληροφορίες εδώ: http://www.pdp.gr/default.asp?pid=1&la=1

[Vangelis]

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


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


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

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

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

http://www.pdp.gr/files/24a/PDP_24_A.pdf

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

[sstergou]

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

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

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

[evry]

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

ΥΓ. Ας με συγχωρήσουν όσοι δεν κατάλαβαν τι εννοώ αλλά προσπαθώ να θίξω το θέμα χωρίς να πω την απάντηση

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

... από που προκύπτει αυτό?

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

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

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

(Αλήθεια, πού είναι το 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.

[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]

Πλάκα πλάκα μια και μιλάμε για διαγωνισμούς, μου ήρθε στο μυαλό μια κατηγορία αλγορίθμων του κλάδου της αλγοριθμικής που λέγεται "Υπολογιστική Γεωμετρία". Το συγκεκριμένο μάθημα διδάσκεται σε ελάχιστα τμήματα πληροφορικής.
Ένα ενδιαφέρον πρόβλημα που εμπίπτει σε αυτή την κατηγορία είναι η εύρεση του λεγόμενου 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]

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