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

Γενικά => Γενικά Παιδαγωγικά, Επιστημονικά και Τεχνικά Θέματα => Διαγωνισμοί => Μήνυμα ξεκίνησε από: Νίκος Αδαμόπουλος στις 28 Νοε 2019, 07:56:02 ΜΜ

Τίτλος: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 28 Νοε 2019, 07:56:02 ΜΜ
http://pdp.gr/

Θέμα Α' Φάσης:
http://pdp.gr/files/32a/PDP_32_A.pdf
έως 2 Φεβρουαρίου.

Κάτι μου θυμίζει!  :-X
Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: evry στις 30 Νοε 2019, 12:27:07 ΜΜ
Τώρα αυτό είναι θέμα για μαθητές Γυμνασίου?
Να δω πόσοι μαθητές Γυμνασίου θα το λύσουν .... (μόνοι τους)
Μεγάλη αλλαγή στη φιλοσοφία σε σχέση με τα άλλα χρόνια.
Μάλλον μπέρδεψαν την Ανάπτυξη Εφαρμογών με τους διαγωνισμούς πληροφορικής!
Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 07 Μαρ 2020, 05:20:25 ΜΜ
Παράθεση από: Νίκος Αδαμόπουλος στις 28 Νοε 2019, 07:56:02 ΜΜ
http://pdp.gr/

Θέμα Α' Φάσης:
http://pdp.gr/files/32a/PDP_32_A.pdf
έως 2 Φεβρουαρίου.

Κάτι μου θυμίζει!  :-X

Θέμα Δ στο Επαναληπτικό του Στεκιού 2012-13:
https://alkisg.mysch.gr/steki/index.php?topic=5173.0
Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: Laertis στις 07 Μαρ 2020, 08:25:54 ΜΜ
 :police:
Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: Νίκος Αδαμόπουλος στις 08 Μαρ 2020, 09:18:56 ΜΜ
Παράθεση από: Νίκος Αδαμόπουλος στις 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; 
}

Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: bugman στις 09 Μαρ 2020, 12:23:08 ΠΜ
Θα το περιγράψω μόνο:
Αρχικά φτιάχνουμε ένα πίνακα με τις διαθέσιμες θέσεις, για τις σχολές.

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

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


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