Ιστοσελίδες μονάδων

Αναφορά προβλημάτων

Διαδικτυακά εργαλεία τεχνικού ελέγχου

Θέμα Α' Φάσης: Ακρόπολη

Η Ακρόπολη των Αθηνών, αποτελεί αν όχι το σημαντικότερο, ένα από τα σημαντικότερα δημιουργήματα της ανθρωπότητας. Η κατασκευή της Ακρόπολης από τη σύλληψη, τη σχεδίαση, τη μελέτη, το κτίσιμο και τη δημιουργία των αιώνιων γλυπτών της αποκαλύπτουν το μεγαλείο του Ελληνικού πολιτισμού.

Ένα από τα πάρα πολλά προβλήματα που είχαν να αντιμετωπίσουν οι Αρχαίοι Έλληνες ήταν αυτό της ανύψωσης των μαρμάρων στον ιερό βράχο. Για να το επιτύχουν χρησιμοποιήσανε ένα σύστημα με τροχαλίες, έτσι ώστε όταν μια άδεια άμαξα κατέρχονταν να χρησιμοποιείται σαν αντίβαρο για την ανερχόμενη. Για την καλλίτερη επίτευξη του πιο πάνω σκοπού, ήταν προτιμότερο οι ελαφρύτερες άμαξες να ανέλθουν πρώτες.

Κατά η δημιουργία των γλυπτών της μετώπης του Παρθενώνα, μερικά ξεχωριστά κομμάτια πεντελικού μαρμάρου έπρεπε να μεταφερθούν άμεσα και σε συγκεκριμένη σειρά. Τα κομμάτια αυτά ήταν μικρά και πρακτικά μικρού βάρους (ενδεικτικό βάρος 1).

Έργο σας είναι να κατασκευάσετε ένα πρόγραμμα το οποίο θα βοηθήσει τους προγόνους μας να προγραμματίσουν την σειρά μεταφοράς των φορτίων. Τα βάρη με την ενδεικτική τιμή 1, αντιστοιχούν σε αυτά τα ξεχωριστά κομμάτια μάρμαρο που πρέπει να μεταφερθούν με τη σειρά που εμφανίζονται.

Αρχεία Εισόδου

Τα αρχεία εισόδου με όνομα acropolis.in είναι αρχεία κειμένου με την παρακάτω δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό N, 1<N<1000 που εκφράζει τον αριθμό των φορτίων που πρέπει να μεταφερθούν. Οι επόμενες Ν γραμμές (2, 3, ... , Ν+1) περιέχουν οι κάθε μία έναν ακέραιο αριθμό Β, 1 <= Β <= 9000. Τα φορτία με Β=1 πρέπει να μεταφερθούν στη σειρά που εμφανίζονται.

Αρχεία Εξόδου

Τα αρχεία εξόδου με όνομα acropolis.out είναι αρχεία κειμένου με την παρακάτω δομή: Έχουν ακριβώς N γραμμές σε κάθε μία από τις υπάρχει ο αριθμός που αντιστοιχεί στη σειρά μεταφοράς των φορτίων και εμφανίζει το βάρος του φορτίου που πρέπει να μεταφερθεί.

Παραδείγματα Αρχείων Εισόδου Εξόδου:

Ενδεικτική λύση σε Pascal

PROGRAM acropolis; (* by Nikos Adamopoulos *)
VAR
  f: Text;
  i, j, tmp, pos, pieces, tosort, p: Integer;
  weights: array [1..1000] of Integer;
  monades: array [1..1000] of Boolean;

BEGIN
  assign(f, 'acropolis.in');
  reset(f);
  readln(f, pieces);
  tosort:=0;
  for i:=1 to pieces do
    begin
      readln(f,p);
      if p=1 then
        monades[i]:=true
      else
        begin
          tosort:=tosort+1;
          weights[tosort]:=p;
          monades[i]:=false;
        end;
    end;
  Close(f);

  for i:=1 to tosort-1 do
    for j:=1 to tosort-i do
      if weights[j]>weights[j+1] then
        begin
          tmp:=weights[j];
          weights[j]:=weights[j+1];
          weights[j+1]:=tmp;
        end;

  assign(f, 'acropolis.out');
  rewrite(f);
  pos:=0;
  for i:=1 to pieces do
    begin
      if monades[i] then
        writeln(f,1)
      else
        begin
          pos:=pos+1;
          writeln(f, weights[pos]);
        end;
    end;
  Close(f);
  halt(0);
END.

Θέμα Β' Φάσης: Απολλώνιες Διαδρομές (Αμφικτιονία των Δελφών)

Στην αρχαία Ελλάδα, οι πόλεις που βρίσκονταν κοντά σε ιερούς χώρους λατρείας συγκροτούσαν «συνδέσμους», τις λεγόμενες αμφικτιονίες, με σκοπό την προάσπιση και διατήρηση των ιερών. Το πλέον σημαντικό ιερό της περιόδου 1000 πΧ – 300 μΧ ήταν αυτό του μαντείου των Δελφών. Η αμφικτιονία των Δελφών υπήρξε για χιλιάδες χρόνια μια αρραγής αμφικτιονία που διατήρησε το μεγαλείο το μαντείου. Το μαντείο των Δελφών ήταν αφιερωμένο στο θεό Απόλλωνα. Οι αρχαίοι πίστευαν ότι οι θεοί επισκέπτονταν τα ιερά και τις πόλεις που προστάτευαν.

Οι αρχαίες Ελληνικές πόλεις συνδέονταν οδικά όπως και οι περισσότερες σύγχρονες πόλεις με περισσότερες από μία διαδρομές. Προφανώς, στην αρχαιότητα δεν υπήρχαν μονόδρομοι, οπότε κάθε δρόμος είναι δύο κατευθύνσεων. Ο θεός Απόλλωνας κάθε φορά που ξεκινώντας από μία πόλη ήθελε να επισκεφτεί μιαν άλλη, μπορούσε να το κάνει με οποιοδήποτε τρόπο αλλά επιθυμούσε να γνωρίζει τη μικρότερη διαδρομή. Έργο σας είναι να υλοποιήσετε ένα πρόγραμμα ώστε να βοηθήσετε τον Απόλλωνα να υπολογίζει το μήκος της συντομότερης διαδρομής, δηλαδή της διαδρομής με την ελάχιστη συνολική απόσταση.

Παρατήρηση για το θέμα: Το μέγιστο μήκος σε στάδια μεταξύ δύο πόλεων είναι 99.

Παράδειγμα

Έστω 6 αρχαίες Ελληνικές πόλεις, μέλη της αμφικτιονίας των Δελφών, οι οποίες είναι συνδεδεμένες οδικά όπως φαίνονται στο παρακάτω σχήμα. Ο Απόλλωνας επιθυμεί να μετακινηθεί από το μαντείο των Δελφών (θέση 1) στην πόλη των Πλαταιών (θέση 6). Η κοντινότερη διαδρομή από τον κόμβο 1 στον κόμβο 6 είναι η 1®2®3®4®6, με συνολικό μήκος 6 (εμφανίζεται στο διάγραμμα με κόκκινο)! Η διαδρομή 1®2®6 έχει μήκος 8, και η διαδρομή 1®5®4®6 έχει μήκος 7.

Αρχεία Εισόδου:

Το αρχείο εισόδου ονομάζεται apollon.in και έχει πάντα την εξής δομή:

• Η πρώτη γραμμή αποτελείται από δύο ακέραιους αριθμούς, Ν (1 < N <= 650) και L (1<= L<= 210925, χωρισμένοι με ένα κενό. O N εκφράζει τον αριθμό των πόλεων (κόμβων) που συγκροτούν την αμφικτιονία, ενώ ο L εκφράζει τον αριθμό των οδών που υπάρχουν.
• Οι επόμενες L γραμμές (2η, 3η, …, L+1) αποτελούνται από τρεις ακεραίους: οι πρώτοι δύο ακέραιοι εκφράζουν τις δύο πόλεις που συνδέει η οδός, ενώ ο τρίτος το μήκος της οδού σε στάδια. Κάθε σύνδεση αναφέρεται μόνο μία φορά.
• Η τελευταία γραμμή του αρχείου (L+2), περιέχει δύο μόνο αριθμούς, τον αριθμό του κόμβου αφετηρίας και του κόμβου τερματισμού.

Αρχεία Εξόδου:

Το αρχείο εξόδου ονομάζεται apollon.out και περιέχει ακριβώς 1 γραμμή, η οποία περιέχει το μήκος της μικρότερης δυνατής διαδρομής μεταξύ των ζητούμενων κόμβων.

Παραδείγματα Αρχείων Εισόδου – Εξόδου:

Μέγιστος χρόνος εκτέλεσης: 5 δευτερόλεπτα.

Ενδεικτική λύση σε Pascal

PROGRAM apollon; (* by Nikos Adamopoulos *)
CONST
  maxt=650;
VAR
  town_dist:array[1..maxt,1..maxt] OF LongInt ;
  distance:array[1..maxt] OF LongInt;
  changed:array[1..maxt] OF Boolean;
  i,j,a,b,L,N,from,dest,ct,cd,nd:LongInt;
  chans:Boolean;
  inpFile:TextFile;
  outFile:Textfile;

BEGIN
  assign(inpFile, 'apollon.in');
  assign(outFile, 'apollon.out');
  reset(inpFile);
  readln(inpFile, N, L);
  FOR i:=1 TO N DO
    BEGIN
      distance[i]:=MaxInt;
      changed[i]:=false;
      FOR j:=1 TO N DO town_dist[i,j]:=MaxInt;
    END;

  FOR i:=1 TO L do
    BEGIN
      readln(inpFile, a, b, cd);
      town_dist[a,b]:=cd;
      town_dist[b,a]:=cd;
    END;

  readln(inpFile, from, dest);
  close(inpFile);

  ct:=from;
  cd:=0;
  distance[ct]:=cd;
  REPEAT
    changed[ct]:=false;
    FOR i:=1 TO N DO
      BEGIN
        nd:=cd+town_dist[ct,i];
        IF nd<distance[i] THEN
          BEGIN
            distance[i]:=nd;
            changed[i]:=true;
          END;
        END;

    chans:=false;
    i:=0;
    REPEAT
      i:=i+1;
      IF changed[i] THEN
        BEGIN
          chans:=true;
          ct:=i;
          cd:=distance[i];
        END;
    UNTIL chans or (i=N);
  UNTIL not chans;

  rewrite(outFile);
  writeln(outFile,distance[dest]);
  close(outFile);
  halt(0);
END.

1ο Θέμα Τελικής Φάσης: Κυκλικός Επιταχυντής

Οι συμμετέχοντες στο camp του 18ου ΠΔΠ, επισκέφθηκαν το νέο Κυκλικό Επιταχυντή Στοιχειωδών Σωματείων (ΚΕΣΣ) Θεσσαλονίκης. Ο επιταχυντής αυτός, περιλαμβάνει N θυρίδες εισόδου σωματείων. Στην είσοδο κάθε θυρίδας τα σωμάτια λαμβάνουν ενέργεια Εⁱⁿ_(Ν) (όπου Ν ο αριθμός της θυρίδας). Κατά την τροχιά τους μέχρι την επόμενη θυρίδα, τα σωμάτια, δαπανούν ενέργεια που αντιστοιχεί σε φράγμα δυναμικού Ε^out_(Ν) που πρέπει να «υπερπηδήσουν». Αν Εⁱⁿ_(Ν) ≥ Ε^out_(Ν) το σωμάτιο θα φθάσει στην επόμενη θυρίδα (Ν+1), στην οποία και θα λάβει ενέργεια Εⁱⁿ_(Ν+1). Η συνολική λοιπόν ενέργεια του σωματίου στην Ν+1 θυρίδα (εφόσον μπήκε στην Ν) θα είναι: (Εⁱⁿ_(Ν) - Ε^out_(Ν) )+ Εⁱⁿ_(Ν+1).

Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα προσδιορίζει την πρώτη (με το μικρότερο αριθμό) θυρίδα από την οποία αν εισέλθει το σωμάτιο, θα ολοκληρώσει μια πλήρη κυκλική τροχιά εντός του επιταχυντή.

ΔΕΔΟΜΕΝΑ ΕΙΣΟΔΟΥ

Το αρχείο cyclotron.in στην πρώτη γραμμή έχει έναν ακέραιο αριθμό που δηλώνει τον αριθμό των θυρίδων εισόδου Ν, όπου: (10 ≤ Ν ≤ 2000000). Στις επόμενες Ν γραμμές δίδονται από δύο ακέραιοι αριθμοί Χ, Υ που ξεχωρίζουν με ένα κενό (0 ≤ X, Y ≤ 1000). Ο πρώτος αριθμός κάθε γραμμής, (Χ) δίνει την ενέργεια (σε eV) που παρέχεται στο σωμάτιο με την είσοδό του στη θυρίδα και ο δεύτερος αριθμός, (Υ) δίνει την ενέργεια που δαπανά το σωμάτιο μέχρι την επόμενη θυρίδα.

ΔΕΔΟΜΕΝΑ ΕΞΟΔΟΥ

Το αρχείο cyclotron.out αποτελείται από έναν ακέραιο που αντιστοιχεί στον αριθμό της θυρίδας από την οποία πρέπει να ξεκινήσει το σωμάτιο ώστε να ολοκληρώσει μια πλήρη κυκλική τροχιά εντός του επιταχυντή. Εάν δεν υπάρχει κατάλληλη θυρίδα εισόδου θα επιστρέφεται ο αριθμός 0.

ΠΑΡΑΔΕΙΓΜΑ ΔΕΔΟΜΕΝΩΝ ΕΙΣΟΔΟΥ - ΕΞΟΔΟΥ

Μέγιστος χρόνος εκτέλεσης: 4 δευτερόλεπτα για κάθε τεστ.

Ενδεικτική λύση σε Pascal

PROGRAM apollon; (* by Nikos Adamopoulos *)
VAR
  portenergy:array[1..2000000] OF LongInt ;
  maxports, firstport, curenergy, curport, steps, i, ein, eout: LongInt;
  done:Boolean;
  inpFile:TextFile;
  outFile:Textfile;

BEGIN
  assign(inpFile, 'cyclotron.in');
  assign(outFile, 'cyclotron.out');
  reset(inpFile);
  readln(inpFile, maxports);
  FOR i:=1 TO maxports DO
    BEGIN
      readln(inpfile, ein, eout);
      portenergy[i]:=ein-eout;
    END;
  close(inpFile);

  firstport:=0;
  done:=false;
  REPEAT
    firstport:=firstport+1;
    curport:=firstport;
    curenergy:=0;
    steps:=0;
    REPEAT
      curenergy:=portenergy[curport]+curenergy;
      steps:=steps+1;
      curport:=curport+1;
      IF curport>maxports THEN curport:=1;
    UNTIL (curenergy<0) or (steps=maxports);
    IF (steps=maxports) and (curenergy>=0) THEN done:=true;
  UNTIL done or (firstport=maxports);

  rewrite(outFile);
  IF done THEN
    writeln(outFile,firstport)
  ELSE
    writeln(outFile,0);
  close(outFile);
  halt(0);
END.

2ο Θέμα Τελικής Φάσης: Επιστημονικά Ενδιαφέροντα

Στο 10o Πανελλήνιο Συνέδριο Πληροφορικής, κάποιοι επιστήμονες είχαν διαφορετικές (επιστημονικές) απόψεις με κάποιους συναδέλφους τους. Για κάθε επιστήμονα γνωρίζουμε με ποιον από τους άλλους επιστήμονες διαφωνεί. (H σχέση "διαφωνία" είναι συμμετρική: Δηλαδή αν ο 1 διαφωνεί με τον 2, τότε και ο 2 διαφωνεί με τον 1)

Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα ελέγχει αν οι επιστήμονες μπορούν να χωριστούν σε δύο ομάδες εργασίας ώστε να μην υπάρχουν διαφωνίες στην ίδια ομάδα (να μην υπάρχουν δηλαδή επιστήμονες στην ίδια ομάδα που θα διαφωνούν μεταξύ τους). Αν αυτό είναι εφικτό, το πρόγραμμα θα πρέπει να υπολογίζει έναν χωρισμό σε δύο ομάδες εργασίας που δεν περιέχουν διαφωνίες. Διαφορετικά, θα πρέπει να διαπιστώνει ότι αυτό δεν είναι εφικτό.

ΔΕΔΟΜΕΝΑ ΕΙΣΟΔΟΥ

Το αρχείο diafonies.in στην πρώτη γραμμή έχει έναν ακέραιο αριθμό που δηλώνει τον αριθμό των επιστημόνων Ν που συμμετείχαν στο συνέδριο, όπου 10 ≤ Ν ≤ 4000. Στις επόμενες N γραμμές δίδονται: Κατά αύξουσα σειρά οι αριθμοί των επιστημόνων, το πλήθος των άλλων επιστημόνων με τους οποίους διαφωνεί κάθε ένας και οι αριθμοί αυτών με αύξουσα σειρά. (Όλοι οι αριθμοί ξεχωρίζουν με ένα κενό).

ΔΕΔΟΜΕΝΑ ΕΞΟΔΟΥ

Το αρχείο diafonies.out περιέχει δύο (2) γραμμές. Σε κάθε μια από τις δύο υπάρχει ο αριθμός που δηλώνει το πλήθος των επιστημόνων της κάθε ομάδας εργασίας και οι αύξοντες αριθμοί των επιστημόνων που τη συγκροτούν. (Πρώτη είναι η ομάδα με το επιστήμονα με το μικρότερο αύξοντα αριθμό). Όλοι οι αριθμοί χωρίζονται με ένα κενό. Σε περίπτωση που οι επιστήμονες δεν είναι δυνατόν να χωριστούν σε δύο ομάδες το αρχείο περιέχει τους αριθμούς 0 σε δύο γραμμές (κενές ομάδες).

ΠΑΡΑΔΕΙΓΜΑ ΔΕΔΟΜΕΝΩΝ ΕΙΣΟΔΟΥ ΕΞΟΔΟΥ

Μέγιστος χρόνος εκτέλεσης: 3 δευτερόλεπτα για κάθε τεστ.

3ο Θέμα Τελικής Φάσης: Πρακτική Άσκηση

Η Ελληνική Εταιρεία Επιστημόνων & Επαγγελματιών Πληροφορικής και Επικοινωνιών (ΕΠΥ) ανέλαβε από το Ακαδημαϊκό Έτος 2006-07 το συντονισμό της πρακτικής άσκησης των φοιτητών των τμημάτων Μηχανικών Η/Υ, Πληροφορικής και Τηλεπικοινωνιών των Ελληνικών Πανεπιστημίων. Στο πρόγραμμα πρακτικής άσκησης δήλωσαν συμμετοχή Ν φοιτητές των αντιστοίχων τμημάτων (4 ≤ Ν ≤ 1000). Οι προσφερόμενες θέσεις πρακτικής άσκησης είναι Μ (N ≤ M ≤ 1500). Ο Πίνακας P [I, J] έχει τιμή 1 αν ο φοιτητής Ι ενδιαφέρεται για τη θέση J και 0 στην αντίθετη περίπτωση.

Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα εξασφαλίζει πρακτική άσκηση σε όσο μεγαλύτερο αριθμό φοιτητών γίνεται.

ΔΕΔΟΜΕΝΑ ΕΙΣΟΔΟΥ

Το αρχείο practice.in στην πρώτη γραμμή έχει δύο αριθμούς: τον αριθμό Ν των ενδιαφερομένων φοιτητών και τον αριθμό Μ των προσφερομένων θέσεων που χωρίζονται με ένα κενό. Κάθε μία από τις επόμενες Ν σειρές περιέχει Μ ψηφία 0 ή 1, τα οποία χωρίζονται μεταξύ τους με ένα κενό και αναπαριστούν τις δηλώσεις των φοιτητών για τις αντίστοιχες θέσεις.

ΔΕΔΟΜΕΝΑ ΕΞΟΔΟΥ

Το αρχείο practice.out περιέχει μία γραμμή με Ν αριθμούς, όπου κάθε αριθμός βρίσκεται στο διάστημα [0..M]. Ο πρώτος αριθμός δηλώνει τη θέση που θα καταλάβει ο πρώτος φοιτητής, ο δεύτερος αριθμός τη θέση που θα καταλάβει ο δεύτερος φοιτητής κοκ. (Φοιτητής με αριθμό 0 σημαίνει ότι δεν βρήκε θέση πρακτικής άσκησης της επιλογής του).

ΠΑΡΑΔΕΙΓΜΑ ΔΕΔΟΜΕΝΩΝ ΕΙΣΟΔΟΥ ΕΞΟΔΟΥ

Μέγιστος χρόνος εκτέλεσης: 5 δευτερόλεπτα για κάθε τεστ.