Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf
Περισσότερες πληροφορίες για το διαγωνισμό: http://www.pdp.gr
Έχουμε καμία προτεινόμενη λύση?
όχι δεν έχουμε, γιατί δεν είναι σωστό να έχουμε πριν λήξει ο διαγωνισμός :police:
Παράθεση από: Νίκος Αδαμόπουλος στις 23 Οκτ 2014, 11:27:07 ΠΜ
Θέμα Α' φάσης:
http://www.pdp.gr/files/27A/PDP_27_A.pdf
Περισσότερες πληροφορίες για το διαγωνισμό: http://www.pdp.gr
Λύση που κατατέθηκε από μαθητή του Γενικού Λυκείου Καλαμπάκα σε 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):#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 από την επιτροπή:#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]
Η λύση με τη στοίβα ενώ είναι αρκετά έξυπνη δεν είναι και τόσο καλή, διότι το συνεχές push/pop έχει κόστος.
Αν το δοκιμάσεις με 1.000.000 στοιχεία τέτοια ώστε να έχει πολλά push/pop είναι πιο αργό από τον απλό τρόπο, με στατικό πίνακα.
Η παρακάτω είναι μια λύση μαθητή του Ζαννείου Γυμνασίου Πειραιά
#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;
}
Όμορφη λύση. Μπράβο στον μαθητή. Από άποψη χώρου σκέφτομαι ότι η χειρότερη περίπτωση είναι να μπουν όλα τα στοιχεία στη στοίβα όταν δοθούν σε φθίνουσα σειρά, οπότε Ο(Ν) 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