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

32ος Πανελλήνιος Διαγωνισμός Πληροφορικής

<< < (2/2)

bugman:
Θα το περιγράψω μόνο:
Αρχικά φτιάχνουμε ένα πίνακα με τις διαθέσιμες θέσεις, για τις σχολές.

Μετά για τους Μαθητές φτιάχνουμε ένα πίνακα 20000 θέσεων, επειδή ξέρουμε ότι δεν υπάρχουν δυο μαθητές με ίδια μόρια. Σε κάθε θέση μπορεί να είναι το Null ή ένα αντικείμενο, το οποίο θα έχει την θέση στην έξοδο και ένα δείκτη σε ένα αντικείμενο Σχολή.
Το αντικείμενο σχολή θα έχει μια ιδιότητα αριθμός σχολής, και ένα δείκτη επόμενη σχολή. Αν το τελευταίο είναι Null σημαίνει δεν έχουμε άλλη σχολή.
Φτιάχνουμε ένα πίνακα με τον αριθμό των σχολών και βάζουμε νούμερα, με αρχική τιμή το 0 να σημαίνει none.

Μόλις τελειώσει το γέμισμα των δομών πάμε στην φάση επεξεργασίας
Ξεκινάμε από το τελευταίο της εικοσιχιλιάδας (που σημαίνει ότι έχει τα περισσότερα μόρια) και κοιτάμε για μη Null. Αν το βρούμε τότε διατρέχουμε την συνδεδεμένη λίστα, ώστε από την πρώτη σχολή παίρνουμε το νούμερο ΧΧ, το βάζουμε στο πίνακα διαθέσιμων θέσεων και αν είναι μη μηδενικός αφαιρούμε ένα και βάζουμε το νούμερο ΧΧ στη θέση στο πίνακα εξόδου που έχουμε καταγράψει στο αντικείμενό μας. Αν βρούμε μηδενική τιμή πάμε στο επόμενο στη συνδεδεμένη λίστα, αν δεν υπάρχει επόμενο πάμε για τον -1 βαθμό, μέχρι να βρούμε πάλι μη μηδενική τιμή, ή τελικά να τερματίσει. Μπορούμε κατά την εισαγωγή βάσει βαθμού να κρατάμε μέγιστο και ελάχιστο ώστε η επανάληψη να γίνει από το μέγιστο ως το ελάχιστο.
Αν Ν είναι οι μαθητές και Ε οι συνολικές επιλογές τότε η χειρότερη περίπτωση είναι όσο οι Ε επιλογές, πχ αν είχαμε 12 επιλογές σχολών για όλους τους μαθητές και η επιλογή ήταν η δωδέκατη τότε θα είχαμε 12*Ν για να γράψουμε τις δομές και 12*Ν να τις διαβάσουμε, δηλαδή το πολύ 24*Ν συν τον μηδενισμό από ελάχιστο ως μέγιστο των βαθμών. Και μένει η εξαγωγή με την ανάγνωση του πίνακα εξόδου (0  για None, >0 για αριθμό σχολής).


Δεν χρειάζεται ανάκτηση της μνήμης από τα αντικείμενα, γιατί η διεργασία τερματίζει και όλη η μνήμη αποδίδεται στο σύστημα

Πλοήγηση

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

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

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