Αποστολέας Θέμα: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής  (Αναγνώστηκε 1429 φορές)

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2804
  • Πύργος Ηλείας
http://pdp.gr/

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

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

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3502
  • to Iterate is human to Recurse divine
Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #1 στις: 30 Νοέ 2019, 12:27:07 μμ »
Τώρα αυτό είναι θέμα για μαθητές Γυμνασίου?
Να δω πόσοι μαθητές Γυμνασίου θα το λύσουν .... (μόνοι τους)
Μεγάλη αλλαγή στη φιλοσοφία σε σχέση με τα άλλα χρόνια.
Μάλλον μπέρδεψαν την Ανάπτυξη Εφαρμογών με τους διαγωνισμούς πληροφορικής!
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2804
  • Πύργος Ηλείας
Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #2 στις: 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

Laertis

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 1508
  • Sky's the limit
    • ΑΣΚΗΣΕΙΣ-ΘΕΜΑΤΑ ΑΕΠΠ
Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #3 στις: 07 Μάρ 2020, 08:25:54 μμ »
 :police:
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2804
  • Πύργος Ηλείας
Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #4 στις: 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.  

bugman

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 480
  • The Bug Eater
    • Πληροφορική Προγραμματισμός
Απ: 32ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #5 στις: 09 Μάρ 2020, 12:23:08 πμ »
Θα το περιγράψω μόνο:
Αρχικά φτιάχνουμε ένα πίνακα με τις διαθέσιμες θέσεις, για τις σχολές.

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

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


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