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

Ξεκίνησε από Νίκος Αδαμόπουλος, 28 Νοε 2019, 07:56:02 ΜΜ

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

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


evry

Τώρα αυτό είναι θέμα για μαθητές Γυμνασίου?
Να δω πόσοι μαθητές Γυμνασίου θα το λύσουν .... (μόνοι τους)
Μεγάλη αλλαγή στη φιλοσοφία σε σχέση με τα άλλα χρόνια.
Μάλλον μπέρδεψαν την Ανάπτυξη Εφαρμογών με τους διαγωνισμούς πληροφορικής!
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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


Laertis

Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

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

Παράθεση από: Νίκος Αδαμόπουλος στις 28 Νοε 2019, 07:56:02 ΜΜ
http://pdp.gr/

Θέμα Α' Φάσης:
http://pdp.gr/files/32a/PDP_32_A.pdf

Μια ενδεικτική λύση με C++ σε O(nlogn):

Κώδικας: C++
#include <cstdio>  
#include <algorithm>  
  
using namespace std;  
  
struct student  
{  
    int aa;  
    int moria;  
} ;  
  
bool comparison(student x, student y)  
{  
    if(x.moria<y.moria)  
        return false;  
    else  
        return true;    
}  
  
  
int main()  
{  
    freopen("erasmus.in", "r", stdin);  
    freopen("erasmus.out", "w", stdout);  
  
    int N, M, i, j, s, u;  
    scanf("%d %d", &N, &M);  
    int X[N], XF[N];  
    for(i=0; i<N; i++) {  
      XF[i]=0;       
      scanf("%d", &X[i]);  
    }  
    student st[M];  
    int K[M], APOT[M], P[M][10];  
    for(i=0; i<M; i++) {  
       st[i].aa=i;   
       scanf("%d %d", &st[i].moria, &K[i]);  
       for(j=0; j<K[i]; j++)   
          scanf("%d", &P[i][j]);    
    }  
      
    sort(st, st+M, comparison);    

    bool ok;  
    for(i=0; i<M; i++) {  
        s=st[i].aa;  
        ok=false;  
        for(j=0; j<K[s]; j++) {  
            u=P[s][j]-1;  
            if (XF[u]<X[u]){  
              XF[u]++;    
              APOT[s]=u+1;  
              ok=true;  
              break;  
            }  
        }  
        if (!ok) APOT[s]=0;  
    }  
    
    for(i=0; i<M; i++) {  
        if (APOT[i]==0)  
            printf("NONE\n");  
        else  
            printf("%d\n", APOT[i]);  
    }  
      
    return 0;  
}


bugman

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

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

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


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