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

Γενικά => Γενικά Παιδαγωγικά, Επιστημονικά και Τεχνικά Θέματα => Διαγωνισμοί => Μήνυμα ξεκίνησε από: Νίκος Αδαμόπουλος στις 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 μμ
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 μμ
http://pdp.gr/

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

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

Κώδικας: C
  1. #include <cstdio>  
  2. #include <algorithm>  
  3.  
  4. using namespace std;  
  5.  
  6. struct student  
  7. {  
  8.     int aa;  
  9.     int moria;  
  10. } ;  
  11.  
  12. bool comparison(student x, student y)  
  13. {  
  14.     if(x.moria<y.moria)  
  15.         return false;  
  16.     else  
  17.         return true;    
  18. }  
  19.  
  20.  
  21. int main()  
  22. {  
  23.     freopen("erasmus.in", "r", stdin);  
  24.     freopen("erasmus.out", "w", stdout);  
  25.  
  26.     int N, M, i, j, s, u;  
  27.     scanf("%d %d", &N, &M);  
  28.     int X[N], XF[N];  
  29.     for(i=0; i<N; i++) {  
  30.       XF[i]=0;      
  31.       scanf("%d", &X[i]);  
  32.     }  
  33.     student st[M];  
  34.     int K[M], APOT[M], P[M][10];  
  35.     for(i=0; i<M; i++) {  
  36.        st[i].aa=i;  
  37.        scanf("%d %d", &st[i].moria, &K[i]);  
  38.        for(j=0; j<K[i]; j++)  
  39.           scanf("%d", &P[i][j]);    
  40.     }  
  41.      
  42.     sort(st, st+M, comparison);    
  43.  
  44.     bool ok;  
  45.     for(i=0; i<M; i++) {  
  46.         s=st[i].aa;  
  47.         ok=false;  
  48.         for(j=0; j<K[s]; j++) {  
  49.             u=P[s][j]-1;  
  50.             if (XF[u]<X[u]){  
  51.               XF[u]++;    
  52.               APOT[s]=u+1;  
  53.               ok=true;  
  54.               break;  
  55.             }  
  56.         }  
  57.         if (!ok) APOT[s]=0;  
  58.     }  
  59.    
  60.     for(i=0; i<M; i++) {  
  61.         if (APOT[i]==0)  
  62.             printf("NONE\n");  
  63.         else  
  64.             printf("%d\n", APOT[i]);  
  65.     }  
  66.      
  67.     return 0;  
  68. }
  69.  
Τίτλος: Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
Αποστολή από: bugman στις 09 Μάρ 2020, 12:23:08 πμ
Θα το περιγράψω μόνο:
Αρχικά φτιάχνουμε ένα πίνακα με τις διαθέσιμες θέσεις, για τις σχολές.

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

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


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