Γενικά > Διαγωνισμοί

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

(1/2) > >>

Νίκος Αδαμόπουλος:
Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf

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

nikosxatz:
Έχουμε καμία προτεινόμενη λύση?

evry:
όχι δεν έχουμε, γιατί δεν είναι σωστό να έχουμε πριν λήξει ο διαγωνισμός  :police:

grdereken:

--- Παράθεση από: Νίκος Αδαμόπουλος στις 23 Οκτ 2014, 11:27:07 πμ ---Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf

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

--- Τέλος παράθεσης ---
Λύση που κατατέθηκε από μαθητή του Γενικού Λυκείου Καλαμπάκα σε Pascal. Προσοχή  τα στοιχεία της ουράς στο κυλικείο δίνονται από το τελευταίο προς τον πρώτο στο αρχείο κειμένου:


--- Κώδικας: Pascal ---PROGRAM ILIAS_GEL_KALAMPAKAS;USES SYSUTILS;VAR  K,N, I,MAX,METR:INTEGER;  SEIRA: ARRAY OF INTEGER;  GRAMMA: CHAR;  NUM : STRING;  INFILE, OUTFILE: TEXT;BEGIN  ASSIGN(INFILE,'xxx.in');  RESET(INFILE);  ASSIGN(OUTFILE,'xxx.out');  REWRITE(OUTFILE); //READING THE NUMBER OF STUDENTS  READLN(INFILE, NUM);  N:=STRTOINT(NUM);//  WRITELN('THE NUMBER OF STUDENTS=', N);  SETLENGTH(SEIRA,N);   //READING THE HEIGHTS OF STUDENTS TO DYNAMIC ARRAY SEIRA  NUM:='';  K:=0;  WHILE NOT EOLN(INFILE) DO     BEGIN     READ(INFILE, GRAMMA);     IF GRAMMA<>' ' THEN     BEGIN       NUM:=CONCAT(NUM, GRAMMA);     END     ELSE     BEGIN      SEIRA[K]:=STRTOINT(NUM);      K:=K+1;      NUM:='';      IF NOT EOLN (INFILE) THEN NUM:='';      END;     END;     SEIRA[K]:=STRTOINT(NUM); //FINDING THE NUMBER OF STUDENTS WHO CAN SEE  MAX:= SEIRA[N-1];  METR:=1; // WRITELN (SEIRA[N-1],' SEE');  FOR I:= N-2 DOWNTO 0 DO    BEGIN      IF SEIRA[I]>MAX THEN        BEGIN          MAX:=SEIRA[I];          METR:= METR + 1;         // WRITELN(SEIRA[I], ' SEE');        END;    END;  WRITELN;//WRITELN(METR, ' STUDENTS CAN SEE');  STR(METR,NUM);  WRITE(OUTFILE,NUM);   CLOSE(INFILE);  CLOSE(OUTFILE);//READLN;  HALT(0);END.
Λύσεις που δόθηκαν από την επιτροπή σε C. H πρώτη ξεκινά από τον πρώτο στην ουρά όπως και η προηγούμενη λύση σε Pascal και απαιτεί χρόνο Ο(N). Η δεύτερη ξεκινά από τον τελευταίο στην ουρά και αν δεν κάνω λαθος απαιτεί χρόνο Ο(N^2):

--- Κώδικας: C ---#undef DEBUG #ifdef DEBUG#define debug(...) fprintf(stderr, __VA_ARGS__)#else#define debug(...) do ; while(0)#define NDEBUG#endif #include <assert.h>#include <stdio.h>#include <vector> using namespace std; int main (){#ifdef CONTEST  freopen("xxx.in", "rt", stdin);  freopen("xxx.out", "wt", stdout);#endif   int N;  scanf("%d\n", &N);  vector<int> x(N);  for (int i=0; i<N; i++)    scanf("%d\n", &(x[i]));   int tallest = x[N-1];  int count = 1;  for (int i=N-2; i>=0; i--)    if (tallest < x[i]) {      tallest = x[i];      count++;    }  printf("%d\n", count);   return 0;}

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

--- Κώδικας: C ---#undef DEBUG #ifdef DEBUG#define debug(...) fprintf(stderr, __VA_ARGS__)#else#define debug(...) do ; while(0)#define NDEBUG#endif #include <assert.h>#include <stdio.h>#include <vector> using namespace std; int main (){#ifdef CONTEST  freopen("xxx.in", "rt", stdin);  freopen("xxx.out", "wt", stdout);#endif   int N;  scanf("%d\n", &N);  vector<int> x(N);  for (int i=0; i<N; i++)    scanf("%d\n", &(x[i]));   int count = 0;  for (int i=0; i<N; i++) {    bool can_see = true;    for (int j=i+1; j<N; j++)      if (x[j] >= x[i]) {        can_see = false;        break;      }    if (can_see) count++;  }  printf("%d\n", count);   return 0;}[code] [b]Και οι τρεις λύσεις απαιτούν χώρο Ο(Ν). Υπάρχει λύση και με στοίβα χωρίς πίνακα Ν στοιχείων, η οποία χρειάζεται λιγότερο χώρο. Η ιδέα είναι να βάζω σε στοίβα κάθε αριθμό που είναι μικρότερος από το στοιχείο της κορυφής. Αν ένα νέο στοιχείο είναι μεγαλύτερο ή ίσο με το στοιχείο της κορυφής βγάζουμε από τη στοίβα όλα τα μικρότερα ή ίσα με αυτό το στοιχείο και βάζουμε αυτό. Στο τέλος τα στοιχεία που υπάρχουν στη στοίβα είναι αυτά που βλέπουν και η κορυφή η απάντηση.[/b]

evry:
Η λύση με τη στοίβα ενώ είναι αρκετά έξυπνη δεν είναι και τόσο καλή, διότι το συνεχές push/pop έχει κόστος.
Αν το δοκιμάσεις με 1.000.000 στοιχεία τέτοια ώστε να έχει πολλά push/pop είναι πιο αργό από τον απλό τρόπο, με στατικό πίνακα.

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


--- Κώδικας: C++ ---#include <fstream>#include <stack>using namespace std;int main() {    ifstream fin("xxx.in");     ofstream fout("xxx.out");    int N, i, x, y;    fin >> N;    stack<int> s;    fin >> x;    s.push(x);    for (i=1; i<N; i++) {        fin >> x;        while (!s.empty() && s.top()<=x)    s.pop();        s.push(x);    }    fout << s.size() << endl;    fin.close(); fout.close();    return 0;}

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση