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

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

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

Θέμα Α' Φάσης: Δέκαθλο

Ένα από τα πλέον όμορφα και ταυτόχρονα δυναμικά Ολυμπιακά Αγωνίσματα είναι το Δέκαθλο. Οι δεκαθλητές, δοκιμάζονται κυριολεκτικά σε δέκα αγωνίσματα στίβου. Στους Ολυμπιακούς Αγώνες της Αθήνας οι δεκαθλητές αγωνίστηκαν σε αυτά τα αγωνίσματα, στις 23 & 24 Αυγούστου 2004. Η τελική κατάταξη προέκυψε από το άθροισμα των βαθμών που συγκέντρωσαν οι αθλητές σε κάθε αγώνισμα. Για λόγους καθαρά στατιστικής, σε κάθε αγώνισμα βγήκε ένας «νικητής» αγωνίσματος. Στο άλμα επί κοντώ, ο νικητής προκύπτει από τους αθλητές που υπερπήδησαν το ίδιο ύψος με μικρότερο αριθμό συνολικών προσπαθειών. Αθλητές με ίδιο αριθμό προσπαθειών που υπερπήδησαν το ίδιο ύψος ανακηρύσσονται εξ ίσου νικητές.

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

ΕΙΣΟΔΟΣ

Το αρχείο εισόδου θα έχει το όνομα dekathlo.txt και την παρακάτω δομή: Η πρώτη γραμμή θα έχει ένα ακέραιο αριθμό Ν που θα δίνει τον αριθμό των αθλητών που συμμετείχαν. Οι επόμενες Ν γραμμές, θα περιέχουν από δύο Υ_Ν, Π_Ν ακέραιους αριθμούς χωριζόμενους από ένα κενό. Ο πρώτος ακέραιος κάθε γραμμής αντιστοιχεί στο ύψος σε εκατοστά που υπερπήδησε κάθε αθλητής και ο δεύτερος ακέραιος στον αριθμό των προσπαθειών του. Η σειρά που περιέχονται οι αριθμοί στο αρχείο, είναι η σειρά συμμετοχής τους στο αγώνισμα.

ΕΞΟΔΟΣ

Το αρχείο εξόδου θα έχει το όνομα nikites.txt και την παρακάτω δομή. Η πρώτη γραμμή περιέχει έναν ακέραιο Χ που θα δίνει το πλήθος των νικητών του αγωνίσματος. Οι επόμενες Χ γραμμές θα περιέχουν από έναν ακέραιο Ι (0 ≤ Χ ≤ Ν) που θα αντιστοιχεί στη σειρά συμμετοχής του κάθε νικητή.

ΠΑΡΑΔΕΙΓΜΑΤΑ:

Περιορισμοί:

1 < Ν ≤ 128, 400 ≤ Υ_Ν ≤ 650 (0: οι άκυρες), 3 ≤ Π_Ν ≤ 30

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

PROGRAM dekathlo; (* by Nikos Adamopoulos *)
VAR
  f1,f2: Text;
  i, athlites, nikites, best_epid, best_prosp: Integer;
  epid: array [1..4000, 1..2] of Integer;

BEGIN
  assign(f1, 'dekathlo.txt');
  reset(f1);
  readln(f1, athlites);
  readln(f1, epid[1,1], epid[1,2]);
  best_epid:=epid[1,1];
  best_prosp:=epid[1,2];
  nikites:=1;  
 
  for i:=2 to athlites do
    begin
      readln(f1, epid[i,1], epid[i,2]);
      if epid[i,1]>best_epid then
        begin
          best_epid:=epid[i,1];
          best_prosp:=epid[i,2];
          nikites:=1;
        end
      else if epid[i,1]=best_epid then
        begin
          if epid[i,2]<best_prosp then
            begin
              best_prosp:=epid[i,2];
              nikites:=1;
            end 
          else if epid[i,2]=best_prosp then
            nikites:=nikites+1; 
        end;
    end;
  Close(f1);
    
  assign(f2, 'nikites.txt');
  rewrite(f2);
  writeln(f2, nikites);
  for i:=1 to athlites do
    if (epid[i,1]=best_epid) and (epid[i,2]=best_prosp) then
      writeln(f2, i);
  Close(f2);
  halt(0);
END.

Θέμα Β' Φάσης: Δημόκριτος

Το Εθνικό Κέντρο Έρευνας Φυσικών Επιστημών "Δημόκριτος" της Ελλάδος, ονομάστηκε έτσι προς τιμή του Έλληνα «πατέρα» της ατομικής θεωρίας Δημόκριτου. Το Ε.Κ.Ε.Φ.Ε. διαθέτει πολλά Ερευνητικά Ινστιτούτα με περισσότερο ίσως γνωστό, το Ινστιτούτο Πυρηνικών Ερευνών. Μια από τις πολλές δραστηριότητες αυτού του Ινστιτούτου, είναι η παραγωγή ραδιενεργών σκευασμάτων που χρησιμοποιούνται για θεραπευτικούς, ερευνητικούς και παραγωγικούς σκοπούς. (π.χ. Ραδιοθεραπείες, Ισοτοπική Επισήμανση, Βιομηχανικές Ακτινογραφίες).

Τα ραδιενεργά σκευάσματα, τοποθετούνται σε ειδικά κιβώτια που δεν επιτρέπουν την εκπομπή ακτινοβολίας μέσα από αυτά. Κάθε κιβώτιο είναι εφοδιασμένο με συσκευή εκπομπής αναγνωριστικού σήματος (ραδιοταυτότητα). Τα κιβώτια αποθηκεύονται σε συγκεκριμένες θέσεις μιας επίπεδης αποθήκης. Μεταξύ των θέσεων αποθήκευσης, σχηματίζεται ένα κανονικό τετραγωνικό πλέγμα από διαδρόμους μετακίνησης. Ο κάθε κόμβος (διασταύρωση) των διαδρόμων μετακίνησης, προσδιορίζεται από ζεύγος συντεταγμένων (x, y). Στην οροφή της αποθήκης και στις «διασταυρώσεις» αυτού του πλέγματος, είναι τοποθετημένοι αισθητήρες υπερβραχέων, με σκοπό την αναγνώριση της θέσης των κιβωτίων. Ο κάθε αισθητήρας έχει συντεταγμένες (x, y) και ένα μοναδικό κωδικό αριθμό, που απεικονίζεται στο σύστημα ελέγχου. Αν ένα κιβώτιο βρεθεί σε μία διασταύρωση (κόμβο), τότε γίνεται αντιληπτό από το αισθητήρα που βρίσκεται ακριβώς πάνω από τον κόμβο και από τους οκτώ πλησιέστερους αισθητήρες προς το συγκεκριμένο κόμβο. Για παράδειγμα ένα κιβώτιο που θα περάσει από τη θέση (0, 0) γίνεται αντιληπτό από τους αισθητήρες: (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1) και τον (0, 0).

Τα κιβώτια μετακινούνται εντός της αποθήκης, με τη βοήθεια αυτόματου ρομποτικού οχήματος μεταφοράς. Προφανώς το ρομπότ μπορεί να μετακινείται στους διαδρόμους μεταξύ των κιβωτίων, κινούμενο πάντοτε παράλληλα ή κάθετα στον άξονα των x. Το ρομπότ ευρισκόμενο σε κάποιο κόμβο, μπορεί να κάνει μια από τις τέσσερις κινήσεις (Up), (Down), (Right), (Left). Κάθε κίνηση R αυξάνει τη τιμή της συντεταγμένης x (τετμημένη) κατά 1. Κάθε κίνηση U αυξάνει τη τιμή της συντεταγμένης y (τεταγμένη) κατά 1. Ως αρχή των κινήσεων του ρομποτικού συστήματος μεταφοράς, νοείται πάντοτε η αρχή των αξόνων (0,0). Στο επόμενο σχήμα, δίνεται ένα απλοποιημένο διάγραμμα διαδρομών με (11 x 11) διασταυρώσεις.

Να αναπτύξετε ένα πρόγραμμα το οποίο θα λαμβάνει σαν είσοδο τις κινήσεις των κιβωτίων και θα παράγει σαν έξοδο:

• Α) Mε αύξουσα σειρά, τους κωδικούς αριθμούς των αισθητήρων που αναγνώρισαν τα κιβώτια.
• Β) Τον αριθμό των διεγέρσεων που δέχθηκε κάθε αισθητήρας.

ΕΙΣΟΔΟΣ

Στην πρώτη γραμμή του αρχείου εισόδου dimokritos.in δίνεται ένας ακέραιος αριθμός N, (όπου 1 < N < 2,000,000), που αντιπροσωπεύει το πλήθος των αισθητήρων. Σε κάθε μία από τις ακόλουθες N γραμμές δίνονται οι συντεταγμένες των αισθητήρων με δύο ακέραιους αριθμούς, Χ και Υ που χωρίζονται με κενό χαρακτήρα, ( όπου -700 < x, y < 700). Η σειρά εμφάνισης των αισθητήρων ταυτίζεται με τον αντίστοιχο κωδικό αριθμό τους.

Στην επόμενη, (N+1)οστή γραμμή, δίνεται ο ακέραιος αριθμός Κ, (όπου 0 <= Κ <= 2,000,000) που δηλώνει το πλήθος των κινήσεων που πραγματοποίησε το ρομποτικό όχημα. Η τελευταία γραμμή περιέχει τους Κ χαρακτήρες που μας εμφανίζουν τη διαδρομή που πραγματοποίησε το όχημα. Οι χαρακτήρες αυτοί μπορεί να είναι U, D, R, L (Κεφαλαία Λατινικά) χωρίς κενό μεταξύ τους. Κάθε γραμμή συμπεριλαμβανομένης της τελευταίας τερματίζεται με τον χαρακτήρα νέας γραμμής και κανένας άλλος χαρακτήρας δεν υπάρχει μετά τον τελευταίο αριθμό κάθε γραμμής.

Σε κάθε περίπτωση το αρχείο εισόδου δεν μπορεί να ξεπερνά τα 2ΜΒ.

ΕΞΟΔΟΣ

Στο αρχείο εξόδου dimokritos.out θα πρέπει να γράψετε τους αριθμούς των αισθητήρων που έχουν «αντιληφθεί» το ρομποτικό όχημα καθώς και τον αριθμό (πλήθος) ων διεγέρσεων που έχει δεχτεί. Οι αριθμοί των αισθητήρων πρέπει να είναι ταξινομημένοι σε αύξουσα σειρά και κάθε αισθητήρας πρέπει να είναι σε με μια χωριστή γραμμή. Ο αριθμός των διεγέρσεων θα ξεχωρίζει με ένα κενό. Εάν κανένας αισθητήρας δεν «αντιλήφθηκε» το όχημα, στη πρώτη και μόνη γραμμή του αρχείου εξόδου πρέπει να γράψετε "-1".

(Παρατήρηση: Θεωρούμε ότι η παρακολούθηση κάθε μετακινούμενου κιβωτίου ξεκινάει όταν αυτό βρεθεί στην αρχή των αξόνων. Επίσης: Από τη στιγμή που κινηθεί το ρομποτικό όχημα μεταφοράς, ενεργοποιούνται και οι 9 αισθητήρες, γύρω και πάνω από την αρχή των αξόνων).

ΠΑΡΑΔΕΙΓΜΑΤΑ:

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

PROGRAM dimokritos; (* by Nikos Adamopoulos *)
VAR
  Sensors:array[-700..700,-700..700] of longint;
  Recordings:array[0..2000000] of longint;
  MoveChars:array[1..2000000] of char;
  SCount,MCount,i,j:longint;
  x,y:integer;
  f:Text;


PROCEDURE RecordTheMove(x, y:integer);
VAR code:longint;
BEGIN
  code:=Sensors[x,y];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x-1,y-1];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x-1,y];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x-1,y+1];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x,y+1];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x+1,y+1];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x+1,y];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x+1,y-1];
  Recordings[code]:=Recordings[code]+1;
  code:=Sensors[x,y-1];
  Recordings[code]:=Recordings[code]+1;
END;


BEGIN
  FOR i:=-700 TO 700 DO
    FOR j:=-700 TO 700 DO
      Sensors[i,j]:=0; 
      
  FOR i:=0 TO 2000000 DO Recordings[i]:=0; assign(f,'dimokritos.in');
  
  reset(f);
  readln(f,SCount); 
  
  FOR i:=1 TO SCount DO
    BEGIN
      readln(f,x,y);
      Sensors[x,y]:=i;
    END;
    
  readln(f,MCount);
  IF MCount>0 THEN
    BEGIN
      readln(f,MoveChars);
      x:=0; y:=0;
      RecordTheMove(x,y); 
      
      FOR i:=1 TO MCount DO
        BEGIN
          CASE MoveChars[i] OF
            'R': x:=x+1;
            'L': x:=x-1;
            'U': y:=y+1;
            'D': y:=y-1;
          END;
          RecordTheMove(x,y);
        END;
    END;
  Close(f); 
 
  assign(f,'dimokritos.out');
  rewrite(f);
  If MCount=0 THEN
    writeln(f,-1)
  ELSE
    FOR i:=1 TO SCount DO
      IF Recordings[i]>0 THEN writeln(f,i,' ',Recordings[i]); 
      
  Close(f);
  halt(0);
END.

1ο Θέμα Τελικής Φάσης: Μοναδικός πολλαπλασιασμός

Προσέξτε το εξής παράδειγμα πολλαπλασιασμού: 48 x 159 = 7.632. Το ενδιαφέρον είναι ότι και τα εννέα ψηφία είναι διαφορετικά χωρίς να περιέχεται το 0.

Κατασκευάστε ένα πρόγραμμα το οποίο θα δέχεται στην είσοδό του ένα αρχείο digits.in. Το αρχείο αυτό θα περιέχει έναν ακέραιο M, όπου 1<=Μ<=98.765.432.

Το πρόγραμμά σας να δίνει στην έξοδο ένα αρχείο digits.out με 1 γραμμή, που θα περιέχει:

• δύο ακεραίους Μ1 και Μ2, έτσι ώστε Μ x M1 = M2 και όλα τα ψηφία των M, M1, M2 να είναι διαφορετικά μεταξύ τους (και χωρίς να περιέχεται το 0). Μεταξύ των δύο αριθμών Μ1 και Μ2 να υπάρχει ένας κενός χαρακτήρας.

είτε

• τον αριθμό 0, αν δεν υπάρχουν κατάλληλα Μ1 και Μ2 ώστε Μ x M1 = M2.

ΠΑΡΑΔΕΙΓΜΑΤΑ:

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

PROGRAM pollaplasiasmos; (* by Nikos Adamopoulos *)
USES math;
VAR
  f:Text;
  m, m1, m2, maxtry:longint;
  mdigits, alldigits: array[0..9] of boolean;
  IsOK: boolean;


PROCEDURE check_m_number(m:longint; VAR valid:boolean);
VAR d, i:integer;
BEGIN
  mdigits[0]:=true;
  FOR i:=1 TO 9 DO
    mdigits[i]:=false;

  valid:=true;
  WHILE valid and (m>0) DO
    BEGIN
      d:=m mod 10;
      m:=m div 10;
      IF mdigits[d] THEN
        valid:=false
      ELSE
        mdigits[d]:=true;
    END;
END;


PROCEDURE check_number(n:longint; VAR valid:boolean);
VAR d, i:integer;
BEGIN
  valid:=true;
  WHILE valid and (n>0) DO
    BEGIN
      d:=n mod 10;
      n:=n div 10;
      IF alldigits[d] THEN
        valid:=false
      ELSE
        alldigits[d]:=true;
    END;
END;


PROCEDURE NewTry;
VAR i:integer;
BEGIN
  FOR i:=0 TO 9 DO
    alldigits[i]:=mdigits[i];
END;


BEGIN
  assign(f, 'digits.in');
  reset(f);
  readln(f, m);
  close(f);
  assign(f, 'digits.out');
  rewrite(f);

  check_m_number(m,IsOK);
  IF IsOK THEN
    BEGIN
      m1:=0;
      maxtry:=ceil(98765432/m);
      IsOK:=false;
      WHILE (m1<maxtry) and (not IsOK) DO
        BEGIN
          NewTry;
          m1:=m1+1;
          check_number(m1,IsOK);
          IF ISOK THEN
            BEGIN
              m2:=m*m1;
              check_number(m2,IsOK);
            END;
        END;
    END;

  IF IsOK THEN writeln(f, m1, ' ', m2) ELSE writeln(f, 0);
  close(f);
  halt(0);
END.

2ο Θέμα Τελικής Φάσης: Κυκλικό ταξίδι

Με το αυτοκίνητό μας πρόκειται να κάνουμε ένα κυκλικό ταξίδι. Δηλαδή θα ξεκινήσουμε από μία αφετηρία, όπου υπάρχει ένα πρατήριο βενζίνης, και θα επιστρέψουμε στο ίδιο σημείο ακολουθώντας την κυκλική διαδρομή. Συνολικά υπάρχουν Ν πρατήρια βενζίνης, και συγκεκριμένα ένα πρατήριο κάθε 100 χιλιόμετρα. Άρα, η συνολική απόσταση που θα διανύσουμε είναι 100*Ν χιλιόμετρα. Το σύνολο της ποσότητας βενζίνης που υπάρχει σε όλα τα πρατήρια αρκεί ακριβώς για τα 100*Ν χιλιόμετρα, ενώ από κάθε πρατήριο μπορούμε να προμηθευτούμε βενζίνη για Χ χιλιόμετρα, όπου 0<=Χ<=100*Ν. Επίσης, υποθέτουμε ότι το ρεζερβουάρ του αυτοκινήτου μας έχει χωρητικότητα για βενζίνη που να αρκεί για 100*Ν χιλιόμετρα.

Το ζητούμενο του προβλήματος είναι να προσδιορίσουμε ένα πρατήριο από όπου πρέπει να ξεκινήσουμε, ώστε να μη μείνουμε από βενζίνη σε κάποιο σημείο του ταξιδιού.

ΕΙΣΟΔΟΣ

Το αρχείο stations.in στην πρώτη γραμμή έχει έναν ακέραιο που δηλώνει τον αριθμό των πρατηρίων Ν, όπου 1<=Ν<=5.000.000. Στις επόμενες Ν γραμμές δίνεται ένας ακέραιος Χ που δηλώνει τον αριθμό των χιλιομέτρων που μπορούμε να διανύσουμε προμηθευόμενοι βενζίνη από το αντίστοιχο πρατήριο.

ΕΞΟΔΟΣ

Το αρχείο stations.out αποτελείται από έναν ακέραιο, που δηλώνει την τάξη του πρατηρίου από όπου πρέπει να ξεκινήσουμε ώστε να μη μείνουμε από βενζίνη στα μέσα της διαδρομής.

ΠΑΡΑΔΕΙΓΜΑ:

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

PROGRAM taksidi; (* by Nikos Adamopoulos *)
VAR
  f:Text;
  pc, start, pnow, r, i:longint;
  pratirio: array[1..5000000] of longint;

BEGIN
  assign(f, 'stations.in');
  reset(f);
  readln(f, pc);
  FOR i:=1 TO pc DO
    readln(f, pratirio[i]);
  close(f);
  assign(f, 'stations.out');
  rewrite(f);

  start:=0;
  REPEAT
    start:=start+1;
    r:=0;
    pnow:=start;
    REPEAT
      r:=r+pratirio[pnow]-100;
      pnow:=pnow+1;
      IF pnow>pc THEN pnow:=1;
    UNTIL (pnow=start) or (r<0);
  UNTIL (pnow=start) and (r>=0);

  writeln(f, start);
  close(f);
  halt(0);
END.

3ο Θέμα Τελικής Φάσης: Ένωση ιδιοκτησιών

Σε μία έκταση υπάρχουν Ν ιδιοκτησίες, όπου κάθε ιδιοκτήτης είναι κάτοχος ενός τμήματος της έκτασης κατά ένα ποσοστό Xi, για 1<=i<=N. Το Xi είναι ένας πραγματικός αριθμός και δηλώνει το αντίστοιχο ποσοστό ιδιοκτησίας. Προφανώς τα ποσοστά όλων των ιδιοκτητών αθροίζουν στο 1 (δηλαδή ΣXi=1). Οι ιδιοκτήτες θέλουν να ενώσουν τις ιδιοκτησίες τους σε μία ενιαία ιδιοκτησία. Ωστόσο, αυτή η διαδικασία μπορεί να γίνει μόνο κατά βήματα. Με λίγα λόγια, στην πρώτη φάση θα ενωθούν δύο ιδιοκτησίες ώστε να αποτελέσουν μια νέα ιδιοκτησία. Έτσι θα προκύψουν συνολικά Ν-1 ιδιοκτησίες, στη συνέχεια από αυτές τις Ν-1 ιδιοκτησίες θα επιλεγούν δύο για ενωθούν κοκ, μέχρι να φθάσουμε σε μία τελική κατάσταση όπου δύο ιδιοκτησίες θα ενωθούν ώστε να αποτελέσουν μία ενιαία έκταση. Σημειώνεται ότι θεωρούμε ότι δύο ιδιοκτησίες μπορούν να ενωθούν ασχέτως αν είναι γειτονικές ή όχι.

Δίνεται ότι το κόστος ένωσης δύο ιδιοκτησιών i και j ισούται με Xi+Xj. Το συνολικό κόστος εξαρτάται από τη σειρά ένωσης των ιδιοκτησιών. Το πρόβλημα έγκειται στον προσδιορισμό του ελάχιστου συνολικού κόστους για την ένωση των εκτάσεων σε μία ενιαία ένωση. Για το σκοπό αυτό πρέπει να κατασκευάσετε ένα πρόγραμμα με τα ακόλουθα χαρακτηριστικά.

ΕΙΣΟΔΟΣ

Το αρχείο land.in στην πρώτη γραμμή έχει έναν ακέραιο που δηλώνει τον αριθμό των ιδιοκτητών N, όπου 1<=Ν<=50.000. Σε κάθε μία από τις επόμενες N γραμμές δίνεται ένας πραγματικός Χ που δηλώνει το ποσοστό ιδιοκτησίας του κάθε ιδιοκτήτη.

ΕΞΟΔΟΣ

Το αρχείο land.out αποτελείται από έναν πραγματικό με στρογγυλοποίηση δύο δεκαδικών ψηφίων, που δηλώνει το ελάχιστο κόστος ένωσης.

ΠΑΡΑΔΕΙΓΜΑΤΑ:

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

PROGRAM idioktisies; (* by Nikos Adamopoulos *)
VAR
  f:Text;
  ic, p1, p2, i, j:longint;
  pososto: array[1..50000] of double;
  min1, min2, kostos: double;

BEGIN
  assign(f, 'land.in');
  reset(f);
  readln(f, ic);
  FOR i:=1 TO ic DO
    readln(f, pososto[i]);
  close(f);
  assign(f, 'land.out');
  rewrite(f);

  kostos:=0;
  FOR i:=ic DOWNTO 2 DO
    BEGIN
      IF pososto[1]<pososto[2] THEN
        BEGIN
          min1:=pososto[1]; p1:=1;
          min2:=pososto[2]; p2:=2;
        END
      ELSE
        BEGIN
          min1:=pososto[2]; p1:=2;
          min2:=pososto[1]; p2:=1;
        END;

      FOR j:=3 TO i DO
        IF pososto[j]<min1 THEN
          BEGIN
            min2:=min1; p2:=p1;
            min1:=pososto[j]; p1:=j;
          END
        ELSE IF pososto[j]<min2 THEN
               BEGIN
                 min2:=pososto[j]; p2:=j;
               END;

      kostos:=kostos+min1+min2;
      pososto[p1]:=min1+min2;
      pososto[p2]:=pososto[i];
    END;

  kostos:=kostos+0.00001;
  writeln(f, kostos:2:2);
  close(f);
  halt(0);
END.

1ο Θέμα Τελικής Συμπληρωματικής Φάσης: Ανάβαση κλίμακας

Για να ανεβούμε στην κορυφή ενός κλιμακοστασίου με Ν σκαλοπάτια, μπορούμε να κάνουμε βήματα του ενός ή των δύο σκαλοπατιών. Το πρόβλημα έγκειται στην εύρεση του πλήθους των διαφορετικών τρόπων ανάβασης, τους οποίους μπορούμε να δοκιμάσουμε προκειμένου να φθάσουμε στην κορυφή του κλιμακοστασίου. Για παράδειγμα, μπορούμε να ανεβούμε Ν=3 σκαλοπάτια με 3 διαφορετικούς τρόπους, δηλαδή: 1-1-1,2-1, 1-2.

ΕΙΣΟΔΟΣ

Ένα αρχείο steps.in που στην πρώτη γραμμή περιέχει έναν ακέραιο Μ (όπου 0<M<=1.000.000) που δηλώνει το πλήθος των περιπτώσεων. Στη συνέχεια ακολουθούν Μ αριθμοί, όπου καθένας δηλώνει το πλήθος Ν (όπου O<N<=50) των σκαλοπατιών ενός κλιμακοστασίου.

ΕΞΟΔΟΣ

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

ΠΑΡΑΔΕΙΓΜΑ:

Χρονικό όριο: 4,5 δευτερόλεπτα

2ο Θέμα Τελικής Συμπληρωματικής Φάσης: Σπάσιμο πιάτων

Η Ελένη και ο Πέτρος έχουν μπροστά τους δύο σωρούς από πιάτα. Ο ένας σωρός έχει Ν1 πιάτα και ο άλλος Ν2 πιάτα. Το παιγνίδι έχει ως εξής. Οι παίκτες εναλλάξ παίρνουν είτε ένα πιάτο από τον ένα σωρό και το σπάνε ή δύο πιάτα (ένα από κάθε σωρό) και τα σπάνε. Ο παίκτης που σπάει το τελευταίο πιάτο κερδίζει. Αρχίζει πάντα το σπάσιμο η Ελένη. Δεδομένων των Ν1 και Ν2, το πρόγραμμά σας θα πρέπει να αποφαίνεται αν κερδίζει ο παίκτης που ξεκινά (δηλαδή, η Ελένη) ή ο παίκτης που παίζει δεύτερος (ο Πέτρος).

ΕΙΣΟΔΟΣ

Ένα αρχείο dishes.in που στην πρώτη γραμμή περιέχει έναν ακέραιο Μ (όπου 0<Μ<=1.000) που δηλώνει το πλήθος των επαναλήψεων. Στη συνέχεια ακολουθούν Μ ζεύγη αριθμών, όπου το κάθε ζεύγος δηλώνει το πλήθος των πιάτων των δύο σωρών, δηλαδή τα Ν1 και Ν2 (όπου 0 < Ν1, Ν2<=1000). Οι δύο αυτοί αριθμοί χωρίζονται με ένα κενό μεταξύ τους.

ΕΞΟΔΟΣ

Ένα αρχείο dishes.out με Μ ακεραίους (ένας ακέραιος ανά γραμμή). Ο ακέραιος είναι 1 αν κερδίζει η Ελένη, και 2 αν κερδίζει ο Πέτρος. Το αρχείο εξόδου πρέπει να τελειώνει με αλλαγή γραμμής.

ΠΑΡΑΔΕΙΓΜΑΤΑ:

• Για N1=l και Μ=1 είναι προφανές ότι κερδίζει η Ελένη (σπάει τα δύο πιάτα και τελειώνει).
• Για Ν2=2 και Μ=2 είναι προφανές ότι χάνει η Ελένη.
  Γιατί: Αν η Ελένη σπάσει ένα από κάθε σωρό, τότε ο Πέτρος σπάει τα δύο που μένουν (ένα σε κάθε σωρό). Αν η Ελένη σπάσει ένα από τον ένα σωρό, τότε ο Πέτρος σπάει το άλλο από τον ίδιο σωρό και στη συνέχεια η Ελένη έχει μόνο μια επιλογή να σπάσει το ένα από τον σωρό με τα δύο και ο Πέτρος σπάει το άλλο και κερδίζει.
• Αν Ν=2 και Μ=3 κερδίζει η Ελένη
  Γιατί: η Ελένη σπάει ένα από τα τρία και ο Πέτρος παίζει με Ν=2 και Μ=2. Όμως σύμφωνα με το προηγούμενο παράδειγμα ο παίκτης που ξεκινά με Ν=2 και Μ=2 πάντα χάνει (άρα χάνει ο Πέτρος).

Χρονικό όριο: 1 δευτερόλεπτο

3ο Θέμα Τελικής Συμπληρωματικής Φάσης: Κροκόδειλοι

Δίνεται το έτος γέννησης και το έτος θανάτου Ν κροκοδείλων. Το πρόβλημα έγκειται στην εύρεση του μέγιστου πλήθους κροκοδείλων σε οποιαδήποτε χρονική στιγμή.

ΕΙΣΟΔΟΣ

Ένα αρχείο crocodiles.in με έναν ακέραιο Ν (όπου 0<Ν<300.000) στην πρώτη γραμμή που δηλώνει το πλήθος των γραμμών που ακολουθούν. Κάθε μία από τις επόμενες γραμμές περιέχει δύο ακεραίους που ανήκουν στο διάστημα [-100000..100000] και δηλώνουν αντίστοιχα το έτος γέννησης και το έτος θανάτου του αντίστοιχου κροκοδείλου. Μεταξύ των ακεραίων υπάρχει ένας κενός χαρακτήρας. Προσοχή, το έτος θανάτου δεν προσμετράται στα έτη ζωής του κροκοδείλου. Δηλαδή αν ένας κροκόδειλος γεννηθεί το 2001 και πεθάνει το 2005, τότε έζησε 4 χρόνια.

ΕΞΟΔΟΣ

Ένα αρχείο crocodiles.out με έναν ακέραιο που δηλώνει το μέγιστο πλήθος ζώντων κροκοδείλων σε οποιαδήποτε χρονική στιγμή. Το αρχείο εξόδου πρέπει να τελειώνει με αλλαγή γραμμής.

ΠΑΡΑΔΕΙΓΜΑ

Χρονικό όριο: 1,2 δευτερόλεπτα