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

Ξεκίνησε από Νίκος Αδαμόπουλος, 23 Οκτ 2014, 11:27:07 ΠΜ

« προηγούμενο - επόμενο »

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

Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf

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

nikosxatz


evry

όχι δεν έχουμε, γιατί δεν είναι σωστό να έχουμε πριν λήξει ο διαγωνισμός  :police:
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

grdereken

#3
Παράθεση από: Νίκος Αδαμόπουλος στις 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 είναι πιο αργό από τον απλό τρόπο, με στατικό πίνακα.

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

Κώδικας: cpp
#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;
}
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

grdereken

Όμορφη λύση. Μπράβο στον μαθητή. Από άποψη χώρου σκέφτομαι ότι η χειρότερη περίπτωση είναι να μπουν όλα τα στοιχεία στη στοίβα όταν δοθούν σε φθίνουσα σειρά, οπότε Ο(Ν) worst case. Από άποψη χρόνου θα γίνουν Ν push λειτουργίες, ενώ όσον αφορά τη λειτουργία pop στη χειρότερη περίπτωση που μόνο ο πρώτος βλέπει και θα μείνει τελικώς στη στοίβα θα γίνουν Ν-1. Οπότε και ο χρόνος παραμένει γραμμικός.   

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

Με δύο μετάλλια στις αποσκευές της επέστρεψε η Εθνική ομάδα πληροφορικής νέων από την 9η Βαλκανική Ολυμπιάδα Πληροφορικής Νέων (JBOI 2015 – http://jboi2015.cs.org.mk/) που διεξήχθη στην πόλη Οχρίδα της FYROM μεταξύ 14 Σεπτεμβρίου 2015 και 19 Σεπτεμβρίου 2015.

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