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

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

<< < (2/3) > >>

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

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

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

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

--- Παράθεση από: 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.

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

Πλοήγηση

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

[#] Επόμενη σελίδα

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

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