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

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

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

Θέμα Α' Φάσης: Το Ψηφιδωτό του Μεγάλου Αλεξάνδρου

Οι αρχαίοι Έλληνες δεν άφησαν πίσω τους μόνο μια ασύλληπτη πνευματική κληρονομιά με τα θεωρητικά έργα τους: Αλλά, και με τα τεχνολογικά τους επιτεύγματα, παρέδωσαν στην ανθρωπότητα έναν τεχνολογικό πολιτισμό, που αν είχε αξιοποιηθεί, οι σημερινές μας δυνατότητες θα ήταν ασύγκριτα μεγαλύτερες. Τα κατασκευαστικά τους θαύματα, όπως ο χιλιομετρητής των Αθηνών, η ατμομηχανή του Ήρωνος, ο αστρολάβος των Αντικυθήρων, οι μηχανές του Αρχιμήδους κα. αποτελούν μερικά από τα πολλά και πολύτιμα δημιουργήματά τους. Εξ’ ίσου σημαντικά ήταν και τα επιτεύγματά τους στις επικοινωνίες. Χρησιμοποιώντας οπτικές ψηφιακές επικοινωνίες από το 12 πΧ. αιώνα μετέφεραν το μήνυμα της νίκης από την Τροία στις Μυκήνες μέσα σε λίγα 24ωρα. Από τα μέσα του 9ου πΧ χρησιμοποίησαν κωδικοποίηση του Ελληνικού αλφαβήτου (Καδμεία γραφή) για τη μετάδοση κειμένων με οπτική κωδικοποίηση σε Καρτεσιανές.

Οι Μακεδόνες, Δωρικό Ελληνικό φύλο με ανθρώπους έχοντες μάκος (μήκος = ψηλούς), έχοντας την ίδια γλώσσα, την ίδια θρησκεία, τα ίδια ήθη και έθιμα αλλά και την ίδια ιστορική διαδρομή με τα άλλα Ελληνικά φύλα, ενοποίησαν επί Φιλίππου του Β΄ (382 – 336 πΧ) τα Ελληνικά Βασίλεια (Πανελλήνια Συμμαχία). Αμέσως μετά, υπό το γιο του, Αλέξανδρο τον Μέγα (356 - 323 πΧ) εγκατέστησαν τη μεγαλύτερη αυτοκρατορία όλων των εποχών. Οι Ρωμαίοι των οποίων η αυτοκρατορία, διαδέχθηκε αυτή του Μ. Αλεξάνδρου, δεν έκρυψαν ποτέ το θαυμασμό τους για το μεγάλο στρατηλάτη. Στην Πομπηία διατηρήθηκε στο μεγαλύτερο μέρος του, ένα από αρχαιότερα ψηφιδωτά που Μεγάλου Αλεξάνδρου, που απεικονίζει το Μ. Αλέξανδρο να νικά τον Δαρείο στη μάχη της Ισσού. Το Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, επί πολλές δεκαετίες διεξάγει συστηματικά αρχαιολογική έρευνα σχετικά με την περίοδο της ακμής του Μακεδονικού Πολιτισμού στον ευρύτερο Ελλαδικό αλλά και διεθνή χώρο. Έκπληκτοι οι ερευνητές του ΑΠΘ, διαπίστωσαν ότι οι χρωματιστές ψηφίδες που χρησιμοποιήθηκαν για την κατασκευή του ψηφιδωτού, είχαν την ίδια χημική σύσταση και με δύο διαφορετικές συγκεντρώσεις Μαγνησίου (Mg) που έχουν διαπιστωθεί μόνο στην ευρύτερη περιοχής της Πέλλας (P) και της Βεργίνας (V) αντίστοιχα! Θραύσματα από άλλα ψηφιδωτά της Ελληνιστικής περιόδου, από όλο το γνωστό τότε κόσμο, επιβεβαίωσαν τα ίδια αποτελέσματα Είναι λοιπόν φανερό, ότι οι Έλληνες βασιλείς και οι Ρωμαίοι αργότερα, θεωρούσαν στοιχείο ισχύος να διακοσμήσουν τα βασίλειά τους με χρωματιστές ψηφίδες από την μητροπολιτική Ελλάδα και μάλιστα από την περιοχή της Μακεδονίας. Το ενδιαφέρον επίσης από τεχνική άποψη, είναι ότι καμία ψηφίδα δεν εφάπτονταν κάθετα ή οριζόντια με ψηφίδα αντίστοιχης προέλευσης. Στο παρακάτω σχήμα δίνεται ένα μεγεθυμένο τμήμα ψηφιδωτού.

Πρόβλημα

Να αναπτύξετε ένα πρόβλημα σε μια από τις γλώσσες του ΙΟΙ το οποίο αφού διαβάσει τις διαστάσεις του ψηφιδωτού και τον τύπο της πρώτης ψηφίδας θα επιστρέφει τη διάταξη των ψηφίδων από τις δύο τοποθεσίες.

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

Τα αρχεία εισόδου με όνομα Alexander.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει δύο αριθμούς. Τον αριθμό των γραμμών 10 ≤ L ≤ 10000 και τον αριθμό των ψηφίδων ανά γραμμή 10 ≤ C ≤ 12000 χωρισμένους με ένα κενό. H δεύτερη γραμμή έχει τον χαρακτήρα P ή V, που αντιστοιχεί στην προέλευση της πρώτης ψηφίδας.

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

Τα αρχεία εξόδου με όνομα Alexander.out είναι αρχεία κειμένου με την εξής δομή: Έχουν L γραμμές των C χαρακτήρων (P ή V) η κάθε μία. Μεταξύ των χαρακτήρων δεν υπάρχει κενό.

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

Οι παρακάτω λύσεις είναι ενδεικτικές χωρίς να σημαίνει ότι είναι κατ’ ανάγκη οι βέλτιστες.

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

(* Ιωσήφ Σάκος (1ο ΕΠΑΛ Ηρακλείου) *)

program alexander;
var 
  A:text;
  L,C:integer;
  M,N:char;
  S:ansistring;

begin
  assign(A,'Alexander.in');
  reset(A);
  readln(A,L,C);
  readln(A,M);
  close(A);
  if M='P' then N:='V' else N:='P';
  S:=M+N;
  repeat
    S:=S+S;
  until length(S)>=C;
  setlength(S,C);
  S:=S+#$0A+N+S;
  setlength(S,C*2+1);
  S:=S+#$0A;
  repeat
    S:=S+S;
  until length(S)>=(C+1)*L;
  setlength(S,(C+1)*L);
  assign(A,'Alexander.out');
  rewrite(A);
  write(A,S);
  close(A);
  halt;
end.

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

/* Ευστάθιος Ουρεϊλίδης (2ο ΓΕΛ Πολίχνης) */

#include <stdio.h>

int main(void)
{
  int i=0, j=0, L, C, Last=1;
  char c, s1[65536], s2[65536];

  FILE *fin = fopen("Alexander.in", "r");
  fscanf(fin, "%d %d\n%c", &L, &C, &c);
  fclose(fin);

  s1[0] = 'P'; s2[0] = 'V';

  for (i=1;i<C;i++) {
    if (Last==1) {
      s1[i] = 'V';
      s2[i] = 'P';
      Last = 2;
    } else
    if (Last==2) {
      s1[i] = 'P';
      s2[i] = 'V';
      Last = 1;
    }
    j = i+1;
  }

  s1[j] = '\n'; s2[j] = '\n';
  if (c=='P') Last = 1; if (c=='V') Last = 2;

  FILE *fout = fopen("Alexander.out", "w");
  for (i=1;i<=L;i++) {
    if (Last==1) {
      Last = 2;
      fwrite(s1, 1, C+1, fout);
    } else
    if (Last==2) {
      Last = 1;
      fwrite(s2, 1, C+1, fout);
    }
  }
  fclose(fout);

  return 0;
}

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

/* Κυριάκος Ίσπογλου (2ο ΓΕΛ Κοζάνης) */

#include <stdio.h>
#include <string.h>

int L, C, i, c;
char *PV, *VP, *bkp, key;

int main( void )
{
  FILE *in = fopen("Alexander.in", "r" );
  FILE *out = fopen("Alexander.out", "w" );

  fscanf( in, "%d %d %c", &L, &C, &key );
  fclose( in );

  PV = new char[ 2*12000 + 3 ];
  VP = new char[ 2*12000 + 3 ];

  memset( PV, 'P', C );
  for( i=1; i<C; i+=2 ) PV[ i ] = 'V';
  PV[ C ] = '\n';
  PV[ C + 1 ] = '\0';

  memset( VP, 'V', C );
  for( i=1; i<C; i+=2 ) VP[ i ] = 'P';
  VP[ C ] = '\n';
  VP[ C + 1 ] = '\0';
 
  if( key == 'V' )
  {
    bkp = PV; PV = VP; VP = bkp;
  }

  strcat( PV, VP );

  for( c=2*C+2, i=0; i<L-1; i+=2 )
  {
    fwrite( PV, c, 1, out );
  }

  if( L % 2 )
  {
    fwrite( PV, C, 1, out );
  }

  delete [] VP;
  delete [] PV;

  fclose( out );
  return 0;
}     

Θέμα B' Φάσης: Χαλκιδικό Αλφάβητο (Μαθητές Λυκείου, ΕΠΑΛ, ΕΠΑΣ)

Ο Εύριπος, το δελφίνι της Χαλκίδας, αφού διέδωσε το Χαλκιδικό¹ αλφάβητο, στην κεντρική Μεσόγειο, αποφάσισε να διακινεί περγαμηνές με το συγκεκριμένο αλφάβητο, στις πολλές παράκτιες πόλεις της Εύβοιας. Η δουλειά του ήταν να παραδίδει γράμματα σε Ν λιμάνια που βρίσκονται σε συντεταγμένες (X_i, Y_i). Ξεκινάει λοιπόν το πρωί από το “σπίτι του” στη θέση (0, 0) και πάει στο “γραφείο του” στη θέση (Α, Β). Το απόγευμα γυρνάει πάλι στο σπίτι του. Ο Εύριπος μπορεί να παραδώσει μόνο κάποια από τα γράμματα καθώς πηγαίνει στη δουλεία του και τα υπόλοιπα καθώς επιστρέφει. Λόγω όμως της παλίρροιας της Χαλκίδας, την πρώτη φορά είναι αναγκασμένος να πηγαίνει μόνο σε σημεία με μεγαλύτερο x από αυτό που ήταν πριν και όταν επιστρέφει, λόγω της αλλαγής του ρεύματος είναι αναγκασμένος να πηγαίνει μόνο σε σημεία με μικρότερο x από αυτό που ήταν πριν.

¹ Οι Έλληνες κάτοικοι της Κύμης (περιοχή της Εύβοιας) το μετέφεραν στην ομώνυμη αποικία τους, Κύμη που ίδρυσαν το 754 π.Χ. στην Κάτω Ιταλία. Από αυτούς διαδόθηκε σε όλη την Ιταλία. Το αλφάβητό τους, επί Ρωμαϊκής αυτοκρατορίας καθιερώθηκε σε όλο το δυτικό κόσμος ως Ρωμαϊκό. Το Χαλκιδικό αλφάβητο περιείχε 7 γράμματα του λεγομένου πλέον λατινικού αλφαβήτου: C, D, F (δίγαμμα), L, P, R, και S!!! Τα αρχαιολογικά ευρήματα επιβεβαιώνουν παντοιοτρόπως ότι το ιδιότυπο «χαλκιδικό» αλφάβητο, στο οποίο το Σ γραφόταν ως C, το Δ ως D, το Ξ ως Χ, το Ρ ως R και το Υ ως U είναι το λατινικό (ετρουσκικό) αλφάβητο.

² Εικόνα: Το «Κύπελλο του Νέστορα» είναι ένα αγγείο από τη Ρόδο. Βρέθηκε σε τάφο της νεκρόπολης της Πιθηκούσας. Δισκοπότηρο που έχει πάνω του χαραγμένο το Ευβοϊκό (Χαλκιδικό) Αλφάβητο!

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο, αφού διαβάσει τα δεδομένα, (συντεταγμένες λιμένων), θα βρίσκει ποια είναι η μικρότερη απόσταση που πρέπει να διανύσει ο Εύριπος έτσι ώστε να παραδώσει όλα τα γράμματα.

Ένα παράδειγμα διαδρομής του Εύριπου δίνεται στο παρακάτω σχήμα (Σπίτι: 0,0 Γραφείο: 15,4):

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

Τα αρχεία εισόδου με το όνομα evripos.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή περιέχουν έναν αριθμό Ν (5 ≤ Ν ≤ 200), τον αριθμό των λιμανιών που πρέπει να επισκεφτεί. Στη δεύτερη γραμμή, υπάρχουν οι συντεταγμένες Α, Β του “γραφείου” του Εύριπου (1 ≤ Α, Β ≤ 1000). Στις επόμενες Ν γραμμές υπάρχουν οι συντεταγμένες Xi, Yi (1 ≤ Χ_i < A και -1000 ≤ Y_i ≤ 1000) των λιμανιών που πρέπει να επισκεφτεί. Όλα τα ζεύγη συντεταγμένων χωρίζονται με ένα κενό.

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

Τα αρχεία εξόδου με το όνομα evripos.out είναι αρχεία κειμένου με την εξής δομή: Έχουν μία μόνο γραμμή που περιέχει έναν μόνο αριθμό. Τον πλησιέστερο ακέραιο, στην ελάχιστη απόσταση που πρέπει να διανύσει ο Εύριπος ώστε να μοιράσει όλα τα γράμματα.

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

Παρατηρήσεις

• Απόσταση δύο σημείων στον δισδιάστατο χώρο d=((Χ₂-Χ₁)^2+(Υ₂-Υ₁)^2)^1/2
• 0 < Χ_i <A
• Όλα τα σημεία έχουν διαφορετικά X_i
• Υπάρχουν τρεις τουλάχιστον αλγοριθμικές επιλύσεις του παραπάνω προβλήματος με πολυπλοκότητα Ο(Ν!), Ο(2^Ν) και Ο(Ν³). Λόγω των χρονικών περιορισμών στην επίλυση του προβλήματος η πρώτη λύση θα βαθμολογηθεί με το 50% της βαθμολογίας, η δεύτερη με 70% - 80% και η τρίτη με το 100% εφόσον δώσουν σωστά αποτελέσματα για τα ανάλογα αρχεία εισόδου
• Στο link http://hellenico.gr/evripos θα βρείτε ένα γραφικό περιβάλλον δοκιμής διαδρομών

Οι παρακάτω λύσεις είναι απολύτως ενδεικτικές.

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

(* Καρύδης Θρασύβουλος (ΓΕΛ Κέρκυρας) *)

PROGRAM evripos;

USES
  SysUtils;

CONST
  MaxPoints = 204;
  INF = 100000;

TYPE
  coordinates = record
    X:integer;
    Y:integer;
  end;
  Coordsys = array[1..MaxPoints] of coordinates;

VAR
  N,
  I,J,K,
  d:integer;
  q:real;
  input,output:text;
  points:Coordsys;
  l:array[1..MaxPoints,1..MaxPoints] of real;

FUNCTION dist(a,b:coordinates):real; //euclidean distiance//
BEGIN
  dist:=sqrt(sqr(a.X-b.X)+sqr(a.Y-b.Y))
END;

PROCEDURE swap(VAR a, b: coordinates);
VAR
  t: integer;
BEGIN
  t := a.X;
  a.X := b.X;
  b.X := t;
  t := a.Y;
  a.Y := b.Y;
  b.Y := t;
END;

FUNCTION Split(start, stop: integer): integer;
VAR
  left, right: integer;
  pivot: integer;
BEGIN
  pivot := points[start].X;
  left := start + 1;
  right := stop;
  WHILE left <= right DO BEGIN
    WHILE (left <= stop) AND (points[left].X < pivot) DO
      left := left + 1;
    WHILE (right > start) AND (points[right].X >= pivot) DO
      right := right - 1;
    IF left < right THEN
      swap(points[left], points[right]);
  END;
  swap(points[start], points[right]);
  Split := right
END;

PROCEDURE QuicksortRecur(start, stop: integer);
VAR
  splitpt: integer;
BEGIN
  IF start < stop THEN BEGIN
    splitpt := Split(start, stop);
    QuicksortRecur(start, splitpt-1);
    QuicksortRecur(splitpt+1, stop);
  END
END;

PROCEDURE Quicksort(size: Integer; VAR points: Coordsys);
BEGIN
  QuicksortRecur(1, size)
END;

BEGIN
  assign(input,'evripos.in');
  reset(input);
  readln(input,N);
  N:=N+2;
  points[1].X:=0;
  points[1].Y:=0;
  FOR I := 2 TO N-1 DO
    readln(input,points[I].X,points[I].Y);
  close(input);
  Quicksort(N, points);
  FOR J := 2 TO N DO
    FOR I := 1 TO J-1 DO
      IF (I=1) AND (J=2) THEN
        l[I,J] := dist(points[i],points[j])
      ELSE IF J>I+1 THEN
        l[I,J]:= l[I,J-1] + dist(points[J-1],points[J])
      ELSE BEGIN
        l[I,J] := INF;
        FOR K := 1 TO I-1 DO BEGIN
          q:= l[K,I] + dist(points[K],points[J]);
          IF q < l[I,J] THEN
            l[I,J]:= q;
        END;
      END;
  d:= Round( l[n-1,n] + dist(points[n-1],points[n]));
  assign(output,'evripos.out');
  rewrite(output);
  writeln(output,d);
  close(output);
end.

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

/* Αρσένης Γεράσιμος (2ο ΓΕΛ Μοσχάτου) */#include <stdio.h>
 
#include <math.h>
#include <stdlib.h>

#define MAX 205

typedef struct {
  int x, y;
} coords;

coords point[MAX];
double a[MAX][MAX];
int n;

double dist(int i, int j) { 
  return sqrt( (point[i].xpoint[j].x)*(point[i].x-point[j].x) 
             + (point[i].ypoint[j].y)*(point[i].y-point[j].y) ); 
}

int cmp(const coords *i, const coords *j) { return i->x - j->x; }

int main() {
  FILE *fin=fopen("evripos.in", "r"), *fout=fopen("evripos.out","w");
  int i, j, k, x, y;
  double min, tmp;

  fscanf(fin, "%d", &n);
  n+=2;
  point[1].x = point[1].y = 0;
  for (i=2; i<=n; i++) {
    fscanf(fin, "%d %d", &x, &y);
    point[i].x=x;
    point[i].y=y;
  }

  qsort(point+1, n, sizeof(coords), cmp);

  a[1][2] = dist(1, 2);

  for (j=2; j<=n; j++)
    for (i=1; i<=j-1; i++) {
      if (i==1 && j==2) a[i][j] = dist(i, j);
      else if (i<j-1)
        a[i][j] = a[i][j-1] + dist(j, j-1);
      else {
        a[i][j] = a[1][i] + dist(1, j);
        for (k=2; k<=i-1; k++) {
          tmp = a[k][i]+dist(k, j);
          if (tmp < a[i][j]) a[i][j] = tmp;
        }
      }
    }

  min = a[n-1][n] + dist(n-1, n);
  fprintf(fout, "%d\n", (int)round(min));
  return 0;
}

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

/* Γαϊτανίδης Απόστολος (Ιδ. ΓΕΛ «Μαντουλίδη») */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define inf 0x3f3f3f3f
#define MAXN 210

typedef struct{
  int x,y;
}point;

double dist(point a,point b){
  return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double min(double a,double b){
  if(a<b)return a;
  else return b;
} 

int cmp(const void *a, const void *b){
  point *c = (point *)a,*d = (point *)b;
  if(c->x >d->x)return 1;
  else return -1;
} 

int n;
point p[MAXN];
double a[MAXN][MAXN];

int main(){
  FILE *fin = fopen("evripos.in","r"),*fout = fopen("evripos.out","w");
  fscanf(fin,"%d",&n);
  p[1].x = p[1].y = 0;
  n+=2;
  for(int i=2;i<=n;i++){
    fscanf(fin,"%d %d",&p[i].x,&p[i].y);
  }
  qsort(p+1, n, sizeof(point), cmp);
  a[1][2] = dist(p[1], p[2]);
  for(int j=2;j<=n;j++){
    for(int i =1;i<=j-1;i++){
      if(i==1 && j==2)a[i][j] = dist(p[i],p[j]);
      else if(j>i+1)a[i][j] = a[i][j-1] + dist(p[j-1],p[j]);
      else {
        a[i][j] = a[1][i] + dist(p[1],p[j]);
        for(int k=1;k<=i-1;k++){
          double q= a[k][i] + dist(p[k],p[j]);
          if(q<a[i][j]){
            a[i][j] = q;
          }
        }
      }
    }
  }
 
  double m = a[n-1][n] + dist(p[n-1],p[n]);
  for (int i=1; i<n; i++) { m = min(m, a[i][n] + dist(p[i],p[n])); }
  fprintf(fout,"%d\n",(int)round(m));
  return 0;
}

Θέμα B' Φάσης: Αναχαιτίσεις στο Αιγαίο (Μαθητές Γυμνασίου)

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

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

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα airforce.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν ακέραιο αριθμό N (10 ≤ N ≤ 1000) που αντιστοιχεί στον αριθμό των εντοπισθέντων ιχνών. Οι επόμενες Ν γραμμές έχουν από μία τριάδα αριθμών x, y, z (-1000 ≤ x, y, z ≤ 1000) που αντιστοιχούν στις τρεις συντεταγμένες ενός ορθοκανονικού συστήματος. Οι αριθμοί χωρίζονται με ένα κενό.

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

Τα αρχεία εξόδου με όνομα airforce.out είναι αρχεία κειμένου με την εξής δομή: Αποτελούνται από μια μόνο γραμμή που έχει δύο αριθμούς χωριζόμενους με ένα κενό. Οι αύξοντες αριθμοί (θέσεις n-1, στο αρχείο airforce.in) των ιχνών που έχουν τη μικρότερη απόσταση.

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

Παρατηρήσεις

• Απόσταση δύο σημείων στον τρισδιάστατο χώρο d=((x₂-x₁)^2+(y₂-y₁)^2+(z₂-z₁)^2)^1/2
• Ο χρόνος υπολογισμού είναι ζωτικής σημασίας για αεροπορικές επιχειρήσεις. Υλοποιήσεις λοιπόν με μικρότερο χρόνο θα έχουν μεγαλύτερη βαρύτητα σε περίπτωση ισοβαθμιών
• Η μέγιστη απόσταση στην οποία μπορούν να αναγνωριστούν δύο αεροσκάφη είναι 10.000 μονάδες απόστασης
• Αν τα δύο εγγύτερα αεροσκάφη είναι το 3ο και το 4ο το αρχείο airforce.out θα έχει τις τιμές [3 4] και όχι [4 3]
• Δεν υπάρχουν περισσότερα από ένα ζεύγη αεροσκαφών με την ίδια μικρότερη απόσταση μεταξύ τους
• Μέγιστος χρόνος εκτέλεσης 5 sec. Μέγιστη επιτρεπτή χρήση μνήμης 5 MB

Οι παρακάτω λύσεις είναι απολύτως ενδεικτικές. Η επίλυση του προβλήματος ανάγονταν ουσιαστικά στην υλοποίηση σε κώδικα του αλγορίθμου εντοπισμού εγγυτέρου ζεύγους.

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

(* Ελευθερίου Θεόδωρος (1ο Γυμνάσιο Μυτιλήνης) *)

program Pdp_2;
var
  a:array[1..1000,1..3] of integer;
  N:integer; {plithos aeroplanwn}
  kk,i,plane1,plane2:integer;
  in_text,out_text:text;
  min,theirdistance:real;

function distance(x1,y1,z1,x2,y2,z2:integer):real;
begin
  distance:=sqrt(sqr(x1-x2)+ sqr(y1-y2)+sqr(z1-z2));
end;

procedure findnearest(k:integer;var kk:integer;var apostasi:real);
var
  x:real;
  i,thesi:integer;
begin
  apostasi:=10001;
  for i:=1 to N do
    begin
     if i<>k then
       begin
         x:=distance(a[i,1],a[i,2],a[i,3],a[k,1],a[k,2],a[k,3]);
         if x<apostasi then
           begin
             apostasi:=x;
             thesi:=i;
           end;
       end;
  end;
  kk:=thesi;
end;

BEGIN
  assign(in_text,'airforce.in');
  reset(in_text);
  readln(in_text,N);
  for i:=1 to N do readln (in_text,a[i,1],a[i,2],a[i,3]);
  close(in_text);
  for i:=1 to N do
    begin
      kk:=0; theirdistance:=0;
      findnearest(i,kk,theirdistance);
      if theirdistance<min then
        begin
          min:=theirdistance;
          plane1:=i;
          plane2:=kk;
        end;
    end;
  assign(out_text,'airforce.out');
  rewrite(out_text);
  writeln(out_text,plane1,' ',plane2);
  close(out_text);
END

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

/* Τσάτσιου Γεωργία (2ο Γυμνάσιο Καλαμπάκας) */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
  FILE *eis;
  FILE *ex;
  int pos,i,j,thesh1,thesh2;
  double t,m;
  int syn[1000][3];

  t=0;
  pos=0;
  m=9999;
  if((eis = fopen("airforce.in", "r")) == NULL) exit(1);
  fscanf(eis,"%d",&pos);
  for(i=0;i<pos;i++) fscanf(eis," %d %d %d",&syn[i][0],&syn[i][1],&syn[i][2]);
  fclose(eis);
  if((ex = fopen("airforce.out", "w")) == NULL) exit(1);
  for(i=0;i<pos;i++){
    for(j=i+1;j<pos;j++){
      t=sqrt(pow((syn[i][0]-syn[j][0]),2)+
             pow((syn[i][1]-syn[j][1]),2)+
             pow((syn[i][2]-syn[j][2]),2));
      if(t<m){thesh1=i;thesh2=j;m=t;}
    }
  }
  thesh1++;
  thesh2++;
  fprintf(ex,"%d %d\n",thesh1,thesh2);
  fclose(ex);
  return(0);
}

1ο Θέμα Τελικής Φάσης: HydroloGIS

Το Εργαστήριο Υδρολογίας του Εθνικού Μετσόβιου Πολυτεχνείου (ΕΜΠ), έχει αναπτύξει ένα Γεωγραφικό Σύστημα Πληροφοριών (Geographic Information Suystem: GIS) για την εποπτεία των υδρολογικών δεδομένων του Ελλαδικού χώρου (http://titan.chi.civil.ntua.gr/website/greece/viewer.htm). Οι υπεύθυνοι υδροπληροφορικής αναπτύσσουν πολλές εφαρμογές για την επεξεργασία σε πραγματικό χρόνο πλειάδας υδρολογικών δεδομένων.

Για τον υπολογισμό των υδάτινων αποθεμάτων, χρησιμοποιούνται πολλές παράμετροι με κυριότερες: τα εκατοστόμετρα βροχόπτωσης Ν και τις ημέρες ηλιοφάνειας (εξατμισοδιαπνοής) Μ, με τους αντίστοιχους συντελεστές a και b για τη λεκάνη απορροής την οποία μελετάμε. Ιδιαίτερο ενδιαφέρον παρουσιάζει το γεγονός ότι με χρήση κατάλληλων συντελεστών, κάθε εκατοστόμετρο βροχής λειτουργεί πολλαπλασιαστικά στα αποθέματα που έχουν συσσωρευτεί προηγούμενα και κάθε μέρα ηλιοφάνειας προσθετικά στην εξάτμιση.

Παραδείγματος χάριν, για 15 εκατοστόμετρα βροχόπτωσης και 100 μέρες ηλιοφάνειας ο συνολικός όγκος νερού που συγκεντρώνεται (σε κυβικά μέτρα) είναι:

V= Vr + a * (1*2*3* … *15)/1000000 – b * (1+2+3+ … +100)

(Vr: Υφιστάμενα αποθέματα, a: συν. συγκέντρωσης, b: συν. εξάτμισης).

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μία από τις γλώσσες του ΙΟΙ το οποίο διαβάζει τις παραπάνω τιμές και υπολογίζει τα υδάτινα αποθέματα μιας λεκάνης απορροής.

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

Τα αρχεία εισόδου, με όνομα hydrologis.in, είναι αρχεία κειμένου, τα οποία περιέχουν πέντε γραμμές με τους ακέραιους αριθμούς N, M, Vr, a, b. Για τους αριθμούς αυτούς ισχύει: (10 < N ≤ 20), (1 ≤ Μ ≤ 365), (1000 ≤ Vr ≤ 1000000), (1 ≤ a, b ≤ 1000).

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

Τα αρχεία εξόδου, με όνομα hydrologis.out, είναι αρχεία κειμένου με την εξής δομή. Έχουν μία γραμμή με ακριβώς έναν ακέραιο αριθμό: τον πλησιέστερο ακέραιο στα κυβικά μέτρα υδάτινων αποθεμάτων V (0 ≤ V ≤ 99999999).

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

Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.

Μέγιστος χρόνος εκτέλεσης: 2 sec.

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

/* Γαϊτανίδης Απόστολος (Ιδ. ΓΕΛ Εκπ/τηρίων Μαντουλίδη) */

#include <stdio.h>
#include <algorithm>
#include <math.h>

#define di 1000000

using namespace std;
typedef unsigned long long ll;
ll a,b,n,m,vr,fj[30],fg[30];
double f[30],fh[30];
FILE *fin = fopen("hydrologis.in","r"), *fout = fopen("hydrologis.out","w");

int main(){
  f[10] = 3.6288;
  fg[10] = 3628800;
  for(ll i = 11;i<=20;i++){
    f[i] = f[i-1] * i;
    fg[i] = fg[i-1]*i;
    fj[i] = (ll)(round(f[i]));
    fh[i] = (double)fg[i]/(double)1000000;
  }
  fscanf(fin,"%llu %llu %llu %llu %llu",&n,&m,&vr,&a,&b);
  double s = (double)(m*(m+1))/(double)(2);
  double ans = (double)vr + (double)a*fh[n] - (double)b*s;
  fprintf(fout,"%llu\n",(ll)round(ans));
  return 0;
}

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

(* Καρύδης Θρασύβουλος (3ο ΓΕΛ Κέρκυρας) *)

program hydroloGIS;
uses
  SysUtils;
var
  a,b,N,M:integer;
  V_R:longint;
  V:longint;
  input,output:text;

function factorial(k:integer):real;
begin
  if ( k=1 ) then
    factorial := 1
  else
    factorial:= factorial(k-1)*k;
end;


function sum(k:integer):longint;
var
  i:integer;
  s:longint;
begin
  s:=0;
  for i := 1 to k do
    s:= s + i;
  sum:=s;
end;

begin
  assign(input,'hydrologis.in');
  reset(input);
  readln(input,N);
  readln(input,M);
  readln(input,V_R);
  readln(input,a);
  readln(input,b);
  V:= round(V_R + a*factorial(N)/1000000 - b*sum(M));
  assign(output,'hydrologis.out');
  rewrite(output);
  writeln(output,V);
  close(output);
end.

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

/* Ουρουελίδης Ευστάθιος (2ο ΓΕΛ Πολίχνης) */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main() {
  int i, N, M, V, Vr, a, b, tmp2;
  double tmp, Va;
  FILE *fin = fopen("hydrologis.in", "r");

  fscanf(fin, "%d %d %d %d %d", &N, &M, &Vr, &a, &b);
  fclose(fin);

  tmp = 1;
  for (i=1;i<=N;i++)
    tmp = ((tmp*1000000) * i)/1000000;
  tmp2 = 0;
  for (i=1;i<=M;i++)
    tmp2 += i;
  Va = Vr + (a * (tmp/1000000)) - (b * tmp2);
  V = (int)(Va+0.5);

  FILE *fout = fopen("hydrologis.out", "w");
  fprintf(fout, "%d\n", V);
  fclose(fout);return 0;
}

2ο Θέμα Τελικής Φάσης: Aegean

To Πανεπιστήμιο Αιγαίου έχει θέσει σε λειτουργία το σύστημα παρακολούθησης σε πραγματικό χρόνο της εμπορικής ναυσιπλοΐας στο Αιγαίο (http://syros-observer.aegean.gr/ais/). Το σύστημα βασίζεται στην καταγραφή του σήματος UHF (Ultra High Frequency) κάθε πλοίου, όπως αυτό λαμβάνεται από ένα ορθοκανονικό δίκτυο παράκτιων κεραιών.

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

Στο παρακάτω σχήμα φαίνεται ένα τέτοιο παράδειγμα: Με έντονα μαύρα γράμματα εμφανίζεται η στάθμη του σήματος που λαμβάνεται σε κάθε κεραία. Είναι φανερό ότι:

1. Το σήμα είναι τόσο μικρότερης στάθμης όσο μακρύτερα βρίσκεται το πλοίο. Η ισχύς Ι δηλαδή του λαμβανομένου σήματος προκύπτει από την σχέση Ι = Ν – Χ (για σύστημα Ν × Ν κεραιών, το εγγύτερο στην κεραία πλοίο έχει σήμα στάθμης Ν και το πλέον απομακρυσμένο 1).

2. Όταν τα πλοία κινούνται σε σειρά ή κατά μέτωπο η αντίστοιχη κεραία (κατά την αρχική φάση του έργου) δέχεται μόνο σήμα από το εγγύτερο πλοίο. (Στο σχήμα μας, η δεύτερη οριζόντια κεραία λαμβάνει μόνο το σήμα από το πλοίο με συντεταγμένες [2, 4]). Κατά τη φάση δοκιμών του συστήματος, έγινε η αντίστροφη διαδικασία. Με βάση τη γνωστή θέση συγκεκριμένων πλοίων, έγινε καταγραφή των σημάτων που έφταναν στις κεραίες λήψεως.

Πρόβλημα:

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

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

Τα αρχεία εισόδου με όνομα aegean.in είναι αρχεία κειμένου με την εξής δομή. Στην πρώτη γραμμή υπάρχει ένας ακέραιος αριθμός Ν (0 ≤ Ν ≤ 199998) που εκφράζει τον αριθμό των πλοίων που εκπέμπουν σήμα. Ακολουθούν Ν γραμμές σε κάθε μία από τις οποίες υπάρχουν οι συντεταγμένες των πλοίων (πρώτα οι τεταγμένες). Στο παράδειγμά μας οι [2, 4], [2, 5], [2, 6], [10, 10].

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

Τα αρχεία εξόδου με όνομα aegean.out είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν αριθμό Δ (10 ≤ Δ ≤ 999999999) τις διαστάσεις (Δ x Δ) της επιτηρούμενης θάλασσας (όλα τα ανιχνεύσιμα πλοία πρέπει να περικλείονται μέσα στις διαστάσεις της επιτηρούμενης θάλασσας.) Στη δεύτερη γραμμή έχουν δύο αριθμούς Μ1, Μ2 (χωρισμένους με ένα κενό) οι οποίοι εκφράζουν αντίστοιχα τον αριθμό των οριζόντιων και των κάθετων κεραιών που εντόπισαν πλοίο (0 ≤ Μ1, Μ2 ≤ Δ). Στις επόμενες Μ1 γραμμές εμφανίζονται με αύξουσα σειρά οι αριθμοί και η αντίστοιχη στάθμη σήματος των οριζόντιων κεραιών που εντόπισαν πλοίο. Στις επόμενες Μ2 γραμμές εμφανίζονται με αύξουσα σειρά οι αριθμοί και η αντίστοιχη στάθμη σήματος των κάθετων κεραιών που εντόπισαν πλοίο. Σε όλες τις κεραίες ο αύξων αριθμός τους και η στάθμη σήματος, χωρίζονται μεταξύ τους με ένα κενό.

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

Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.

Μέγιστος χρόνος εκτέλεσης: 5 sec.

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

/* Μπιτζές Γεώργιος (1ο ΓΕΛ Κερατσινίου) */

#include <stdio.h>
#include <map>

using namespace std;

map<int, int> horiz;
map<int, int> vert;

int D = 0;
int horCount = 0;
int vertCount = 0;
int horizontals[200000];
int verticals[200000];
int N;

int process(int x, int y)
{
  if(x > D) D = x;
  if(y > D) D = y;
  if(horiz[x] == 0) { horizontals[++horCount] = x; horiz[x] = y; }
  if(vert[y] == 0) { verticals[++vertCount] = y; vert[y] = x; }
  if(horiz[x] > y) horiz[x] = y;
  if(vert[y] > x) vert[y] = x;
}

int compare(const void *a, const void *b)
{
  return *(int*)a - *(int*)b;
}

int readFile(void)
{
  FILE *in = fopen("aegean.in", "r");
  fscanf(in, "%d", &N);
  int i, x, y;
  for(i = 1; i <= N; i++)
  {
    fscanf(in, "%d %d", &x, &y);
    process(x, y);
  }
}

int output(void)
{
  FILE *out = fopen("aegean.out", "w");
  fprintf(out, "%d\n", D);
  fprintf(out, "%d %d\n", horCount, vertCount);
  qsort(horizontals+1, horCount, sizeof(int), compare);
  qsort(verticals+1, vertCount, sizeof(int), compare);
  int i;
  for(i = 1; i <= horCount; i++)
    fprintf(out, "%d %d\n", horizontals[i], D+1 - horiz[horizontals[i]]);
  for(i = 1; i <= vertCount; i++)
    fprintf(out, "%d %d\n", verticals[i], D+1 - vert[verticals[i]]);
  fclose(out);
}

int main(void)
{
  readFile();
  output();
  return 0;
}

3ο Θέμα Τελικής Φάσης: CPU

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

Τα κυκλώματα απαιτείται να συνδεθούν μεταξύ τους με καλωδιακές συνδέσεις. Οι συνδέσεις δεν πρέπει να διασταυρώνονται με τα κυκλώματα ή με άλλες συνδέσεις, αλλά δεν είναι αναγκαίο να ακολουθήσουν ευθείες γραμμές.

Οι φοιτητές έχουν ήδη κάνει τη βασική σχεδίαση, στην οποία όλα τα εξαρτήματα είναι συνδεδεμένα μεταξύ τους σε ένα βρόχο, τον οποίο καλούμε κύριο βρόχο. (Αυτές οι συνδέσεις είναι το 1 με το 2, το 2 με το 3, …, το Ν με το 1). Τα κυκλώματα στον κύριο βρόχο είναι διαδοχικά αριθμημένα.

Για να αυξηθεί η ταχύτητα του επεξεργαστή, απαιτείται να συνδεθούν απ’ ευθείας κάποια από τα ζευγάρια των εξαρτημάτων. Για κάθε εξάρτημα θα ήταν επιθυμητό να προστεθεί το πολύ μία επιπλέον σύνδεση. Οι φοιτητές έχουν φτιάξει μια λίστα με όλες τις συνδέσεις που θέλουν να προσθέσουν και τις έχουν ταξινομήσει με βάση τη σειρά προτεραιότητάς τους (σημασία τους). Θα προσθέσουν τις K πιο σημαντικές από αυτές τις συνδέσεις, όπου το Κ πρέπει να είναι όσο πιο μεγάλο γίνεται χωρίς να επιβάλλει διασταυρώσεις καλωδίων.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μία από τις γλώσσες του ΙΟΙ το οποίο θα προσδιορίσει τη μέγιστη δυνατή τιμή του Κ.

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

Τα αρχεία εισόδου με όνομα cpu.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή του αρχείου περιέχει ένα ακέραιο N (όπου 1 ≤ N ≤ 200.000) ο οποίος εκφράζει τον αριθμό των εξαρτημάτων που ήδη οι φοιτητές έχουν στον κύριο βρόχο. Η δεύτερη γραμμή περιέχει έναν ακέραιο M (όπου 1 ≤ M ≤ 50.000), ο οποίος εκφράζει τον αριθμό των επιπλέον συνδέσεων τις οποίες οι φοιτητές σκοπεύουν να προσθέσουν. Οι υπόλοιπες M γραμμές περιέχουν δύο θετικούς ακέραιους P και Q, που δείχνουν ότι οι φοιτητές θέλουν να συνδέσουν το εξάρτημα P με το εξάρτημα Q.

Προσοχή: Δεν υπάρχει καμία σύνδεση ενός εξαρτήματος με τον εαυτό του, κάθε εξάρτημα μπορεί να είναι συνδεδεμένο με ένα γειτονικό εξάρτημα στον κύριο βρόχο. Οι συνδέσεις είναι καταγεγραμμένες με φθίνουσα σειρά σημαντικότητας.

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

Τα αρχεία εξόδου με όνομα cpu.out είναι αρχεία κειμένου με την εξής δομή: Έχει ακριβώς μία γραμμή που θα περιέχει έναν απλό ακέραιο, τη μέγιστη δυνατή τιμή του Κ.

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

Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.

Μέγιστος χρόνος εκτέλεσης: 4 sec.

Εξήγηση: προστίθενται οι συνδέσεις 1-4 και 3-6. Μετά, η σύνδεση 2-5 επιβάλλει διασταύρωση και άρα δεν μπορεί να προστεθεί.

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

/* Παναγιωτάκος Γεώργιος (1ο ΓΕΛ Σπάρτης) */

#include <iostream>
#include <fstream>

using namespace std;

int n,m;
int C[50000][2];
int ins[50000][2],outs[50000][2];
int insN=0,outsN=0;
int c[2][100000][2];
int cN[2]={0,0};

bool pos( int a1,int a2,int node ) {
  int m1,m2;
  m1 = min(a1,a2);
  m2 = max(a1,a2);
  if( node>m1 && node<m2 ) return true;
  else return false;
}

int valid(int cn,int a,int b) {
  int i=0,e;
  for(e=0;e<cN[cn];e++) {
    if( c[cn][e][0] == -1 ) continue;
    if( pos(c[cn][e][0],c[cn][e][1],a) != pos(c[cn][e][0],c[cn][e][1],b) )
      return e;
  }
  return -1;//<--valid
}

int min( int a,int b ) {
  return ((a<b)?a:b);
}

int max( int a,int b) {
  return ((a>b)?a:b);
}

bool change( int cn,int ind ) {
  int o1,o2;
  o1 = valid(1-cn,c[cn][ind][0],c[cn][ind][1]);
  if( o1 == -1 ) {
    return -2;
    c[1-cn][cN[1-cn]][0] = c[cn][ind][0];
    c[1-cn][cN[1-cn]][1] = c[cn][ind][1];
    cN[1-cn]++;
    c[cn][ind][0] = -1;
    c[cn][ind][1] = -1;
    }//<-success
  else return -1;//<--failure
}

int main() {
  ifstream fin( "cpu.in" );
  ofstream fout( "cpu.out" );
  fin >> n;
  fin >> m;
  int u,i0,i1,i2,e,a,b,sol;
  sol = m;
  for(u=0;u<m;u++) {
    fin >> a >> b;
    //cout << a << " " << b << "\n";
    C[u][0] = a;
    C[u][1] = b;
    i0 = valid(0,a,b);
    if( i0 == -1 ) { 
      c[0][cN[0]][0] = a;
      c[0][cN[0]][1] = b;
      cN[0]++;
      continue; 
    }
    //cout << u << "Not in the first\n";
    i1 = valid(1,a,b);
    if( i1 == -1 ) { 
      c[1][cN[1]][0] = a;
      c[1][cN[1]][1] = b;
      cN[1]++;
      continue; 
    }
    //cout << u << "Not in the second\n";
    i0 = change( 0, i0 );
    if( i0 == -2 ) { 
      c[0][cN[0]][0] = a;
      c[0][cN[0]][1] = b;
      cN[0]++;
      continue; 
    }
    i1 = change( 1, i1 );
    if( i1 == -2 ){ 
      c[1][cN[1]][0] = a;
      c[1][cN[1]][1] = b;
      cN[1]++;
      continue; 
    }
    
    sol = u;
    break;
  }
  fout << sol << "\n";
  //cout << sol << "\n";
  return 0;
}

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

/* Αρσένης Γεράσιμος (2ο ΓΕΛ Μοσχάτου) */

#include <stdio.h>

#define MAX 50005

void swap(int *a, int *b) {
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
  return;
}

struct vert {
  int x, y;
};

int diff_side(int a, int b, int c, int d) {
  if (d<b && d>a && (c>b || c<a)) return 1;
  if (c<b && c>a && (d>b || d<a)) return 1;
  return 0;
}

int main() {
  FILE *fin=fopen("cpu.in", "r"), *fout=fopen("cpu.out", "w");
  int n, m, x, y, i, j, type[MAX], t1, t2;
  struct vert cpu[MAX];

  fscanf(fin, "%d %d", &n, &m);
  for (i=1; i<=m; i++) {
    fscanf(fin, "%d %d", &x, &y);
    if (x>y) swap(&x, &y);
    cpu[i].x = x;
    cpu[i].y = y;
    t1=t2=0;
    for (j=1; j<i; j++)
      if (diff_side(x, y, cpu[j].x, cpu[j].y)) { 
        if (type[j]==1) { t1++; } else { t2++; } 
      }
    //printf("%d\n", cnt);
    if (t1 && t2) { fprintf(fout, "%d\n", i-1); return 0; }
    if (t1) type[i] = 2;
    else type[i] = 1;
  }
  //printf("diff: %d\n", diff_side(1, 4, 3, 6));
  fprintf(fout, "%d\n", m);
  return 0;
}