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

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2780
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf

Περισσότερες πληροφορίες για το διαγωνισμό: http://www.pdp.gr

nikosxatz

  • Νέος
  • *
  • Μηνύματα: 7
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #1 στις: 20 Νοέ 2014, 11:13:14 πμ »
Έχουμε καμία προτεινόμενη λύση?

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #2 στις: 20 Νοέ 2014, 11:33:48 πμ »
όχι δεν έχουμε, γιατί δεν είναι σωστό να έχουμε πριν λήξει ο διαγωνισμός  :police:
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

grdereken

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 30
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #3 στις: 23 Φεβ 2015, 06:52:04 μμ »
Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf

Περισσότερες πληροφορίες για το διαγωνισμό: http://www.pdp.gr
Λύση που κατατέθηκε από μαθητή του Γενικού Λυκείου Καλαμπάκα σε Pascal. Προσοχή  τα στοιχεία της ουράς στο κυλικείο δίνονται από το τελευταίο προς τον πρώτο στο αρχείο κειμένου:

Κώδικας: Pascal
  1. PROGRAM ILIAS_GEL_KALAMPAKAS;
  2. USES SYSUTILS;
  3. VAR
  4.   K,N, I,MAX,METR:INTEGER;
  5.   SEIRA: ARRAY OF INTEGER;
  6.   GRAMMA: CHAR;
  7.   NUM : STRING;
  8.   INFILE, OUTFILE: TEXT;
  9. BEGIN
  10.   ASSIGN(INFILE,'xxx.in');
  11.   RESET(INFILE);
  12.   ASSIGN(OUTFILE,'xxx.out');
  13.   REWRITE(OUTFILE);
  14.  
  15. //READING THE NUMBER OF STUDENTS
  16.   READLN(INFILE, NUM);
  17.   N:=STRTOINT(NUM);
  18. //  WRITELN('THE NUMBER OF STUDENTS=', N);
  19.   SETLENGTH(SEIRA,N);
  20.  
  21.   //READING THE HEIGHTS OF STUDENTS TO DYNAMIC ARRAY SEIRA
  22.   NUM:='';
  23.   K:=0;
  24.   WHILE NOT EOLN(INFILE) DO
  25.      BEGIN
  26.      READ(INFILE, GRAMMA);
  27.      IF GRAMMA<>' ' THEN
  28.      BEGIN
  29.        NUM:=CONCAT(NUM, GRAMMA);
  30.      END
  31.      ELSE
  32.      BEGIN
  33.       SEIRA[K]:=STRTOINT(NUM);
  34.       K:=K+1;
  35.       NUM:='';
  36.       IF NOT EOLN (INFILE) THEN NUM:='';
  37.       END;
  38.      END;
  39.      SEIRA[K]:=STRTOINT(NUM);
  40.  
  41. //FINDING THE NUMBER OF STUDENTS WHO CAN SEE
  42.   MAX:= SEIRA[N-1];
  43.   METR:=1;
  44.  // WRITELN (SEIRA[N-1],' SEE');
  45.   FOR I:= N-2 DOWNTO 0 DO
  46.     BEGIN
  47.       IF SEIRA[I]>MAX THEN
  48.         BEGIN
  49.           MAX:=SEIRA[I];
  50.           METR:= METR + 1;
  51.          // WRITELN(SEIRA[I], ' SEE');
  52.         END;
  53.     END;
  54.   WRITELN;
  55. //WRITELN(METR, ' STUDENTS CAN SEE');
  56.   STR(METR,NUM);
  57.   WRITE(OUTFILE,NUM);
  58.  
  59.   CLOSE(INFILE);
  60.   CLOSE(OUTFILE);
  61. //READLN;
  62.   HALT(0);
  63. END.

Λύσεις που δόθηκαν από την επιτροπή σε C. H πρώτη ξεκινά από τον πρώτο στην ουρά όπως και η προηγούμενη λύση σε Pascal και απαιτεί χρόνο Ο(N). Η δεύτερη ξεκινά από τον τελευταίο στην ουρά και αν δεν κάνω λαθος απαιτεί χρόνο Ο(N^2):

Κώδικας: C
  1. #undef DEBUG
  2.  
  3. #ifdef DEBUG
  4. #define debug(...) fprintf(stderr, __VA_ARGS__)
  5. #else
  6. #define debug(...) do ; while(0)
  7. #define NDEBUG
  8. #endif
  9.  
  10. #include <assert.h>
  11. #include <stdio.h>
  12. #include <vector>
  13.  
  14. using namespace std;
  15.  
  16. int main ()
  17. {
  18. #ifdef CONTEST
  19.   freopen("xxx.in", "rt", stdin);
  20.   freopen("xxx.out", "wt", stdout);
  21. #endif
  22.  
  23.   int N;
  24.   scanf("%d\n", &N);
  25.   vector<int> x(N);
  26.   for (int i=0; i<N; i++)
  27.     scanf("%d\n", &(x[i]));
  28.  
  29.   int tallest = x[N-1];
  30.   int count = 1;
  31.   for (int i=N-2; i>=0; i--)
  32.     if (tallest < x[i]) {
  33.       tallest = x[i];
  34.       count++;
  35.     }
  36.   printf("%d\n", count);
  37.  
  38.   return 0;
  39. }


2η λύση σε C από την επιτροπή:

Κώδικας: C
  1. #undef DEBUG
  2.  
  3. #ifdef DEBUG
  4. #define debug(...) fprintf(stderr, __VA_ARGS__)
  5. #else
  6. #define debug(...) do ; while(0)
  7. #define NDEBUG
  8. #endif
  9.  
  10. #include <assert.h>
  11. #include <stdio.h>
  12. #include <vector>
  13.  
  14. using namespace std;
  15.  
  16. int main ()
  17. {
  18. #ifdef CONTEST
  19.   freopen("xxx.in", "rt", stdin);
  20.   freopen("xxx.out", "wt", stdout);
  21. #endif
  22.  
  23.   int N;
  24.   scanf("%d\n", &N);
  25.   vector<int> x(N);
  26.   for (int i=0; i<N; i++)
  27.     scanf("%d\n", &(x[i]));
  28.  
  29.   int count = 0;
  30.   for (int i=0; i<N; i++) {
  31.     bool can_see = true;
  32.     for (int j=i+1; j<N; j++)
  33.       if (x[j] >= x[i]) {
  34.         can_see = false;
  35.         break;
  36.       }
  37.     if (can_see) count++;
  38.   }
  39.   printf("%d\n", count);
  40.  
  41.   return 0;
  42. }[code]
  43.  
  44. [b]Και οι τρεις λύσεις απαιτούν χώρο Ο(Ν). Υπάρχει λύση και με στοίβα χωρίς πίνακα Ν στοιχείων, η οποία χρειάζεται λιγότερο χώρο. Η ιδέα είναι να βάζω σε στοίβα κάθε αριθμό που είναι μικρότερος από το στοιχείο της κορυφής. Αν ένα νέο στοιχείο είναι μεγαλύτερο ή ίσο με το στοιχείο της κορυφής βγάζουμε από τη στοίβα όλα τα μικρότερα ή ίσα με αυτό το στοιχείο και βάζουμε αυτό. Στο τέλος τα στοιχεία που υπάρχουν στη στοίβα είναι αυτά που βλέπουν και η κορυφή η απάντηση.[/b]
« Τελευταία τροποποίηση: 07 Μάρ 2015, 08:22:07 μμ από grdereken »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #4 στις: 23 Φεβ 2015, 07:30:24 μμ »
Η λύση με τη στοίβα ενώ είναι αρκετά έξυπνη δεν είναι και τόσο καλή, διότι το συνεχές push/pop έχει κόστος.
Αν το δοκιμάσεις με 1.000.000 στοιχεία τέτοια ώστε να έχει πολλά push/pop είναι πιο αργό από τον απλό τρόπο, με στατικό πίνακα.

Η παρακάτω είναι μια λύση μαθητή του Ζαννείου Γυμνασίου Πειραιά

Κώδικας: C++
  1. #include <fstream>
  2. #include <stack>
  3. using namespace std;
  4. int main() {
  5.     ifstream fin("xxx.in");     ofstream fout("xxx.out");
  6.     int N, i, x, y;
  7.     fin >> N;
  8.     stack<int> s;
  9.     fin >> x;
  10.     s.push(x);
  11.     for (i=1; i<N; i++) {
  12.         fin >> x;
  13.         while (!s.empty() && s.top()<=x)    s.pop();
  14.         s.push(x);
  15.     }
  16.     fout << s.size() << endl;
  17.     fin.close(); fout.close();
  18.     return 0;
  19. }
  20.  
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

grdereken

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 30
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #5 στις: 25 Φεβ 2015, 10:06:41 μμ »
Όμορφη λύση. Μπράβο στον μαθητή. Από άποψη χώρου σκέφτομαι ότι η χειρότερη περίπτωση είναι να μπουν όλα τα στοιχεία στη στοίβα όταν δοθούν σε φθίνουσα σειρά, οπότε Ο(Ν) worst case. Από άποψη χρόνου θα γίνουν Ν push λειτουργίες, ενώ όσον αφορά τη λειτουργία pop στη χειρότερη περίπτωση που μόνο ο πρώτος βλέπει και θα μείνει τελικώς στη στοίβα θα γίνουν Ν-1. Οπότε και ο χρόνος παραμένει γραμμικός.   

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

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2780
  • Πύργος Ηλείας
    • ΚΕΠΛΗΝΕΤ Ηλείας
Απ: 27ος Πανελλήνιος Διαγωνισμός Πληροφορικής
« Απάντηση #6 στις: 28 Σεπ 2015, 11:17:17 μμ »
Με δύο μετάλλια στις αποσκευές της επέστρεψε η Εθνική ομάδα πληροφορικής νέων από την 9η Βαλκανική Ολυμπιάδα Πληροφορικής Νέων (JBOI 2015 – http://jboi2015.cs.org.mk/) που διεξήχθη στην πόλη Οχρίδα της FYROM μεταξύ 14 Σεπτεμβρίου 2015 και 19 Σεπτεμβρίου 2015.

http://www.pdp.gr/files/27DT/DT_JBOI2015.pdf