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

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

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

Θέμα Α' Φάσης: Αυτοκίνητα Υδρογόνου

Αποτελεί πλέον κοινή παραδοχή ότι το υφιστάμενο μοντέλο ανάπτυξης, πέραν όλων των άλλων στρεβλώσεων προκαλεί μια τρομακτική υποβάθμιση στο περιβάλλον του πλανήτη μας. Η μείωση της καύσης υδρογονανθράκων και ο περιορισμός της ποσότητας του εκπεμπόμενου διοξειδίου του άνθρακα (CO₂), αποτελούν πρώτιστη προτεραιότητα για την ανθρωπότητα. Η χρήση Υδρογόνου (H₂), που μπορεί να παραχθεί φθηνά από το θαλασσινό νερό με ηλεκτρόλυση, τα ηλεκτρικά φορτία της οποίας μπορούν να μας τα παρέχουν φωτοβολταϊκά στοιχεία, είναι μια ελπιδοφόρα λύση. Η ένωση του H₂ με το Οξυγόνο (Ο₂) γίνεται με ισχυρή εξώθερμη αντίδραση και μόνο κατάλοιπο το νερό! (2H₂ + O₂ --> 2H₂O). Η ελεγχόμενη αντίδραση σε «κυψέλες υδρογόνου» παράγει ηλεκτρικό ρεύμα.

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

Πρόβλημα

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

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

Τα αρχεία με όνομα hydrogen.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό. Τον αριθμό των τμημάτων για τα οποία υπήρξαν αναφορές βλάβης 10 ≤ C ≤ 10000. Οι επόμενες C γραμμές περιέχουν οι κάθε μία δύο ακέραιους αριθμούς χωριζόμενους από ένα κενό. Τον αριθμό του τμήματος και τις συνολικές βλάβες που διαπιστώθηκαν.

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

Τα αρχεία με όνομα hydrogen.out είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό. Τον αριθμό των τμημάτων τα οποία παρουσίασαν βλάβη ευθύνης του κατασκευαστή 0 ≤ L ≤ 10000. Οι επόμενες L γραμμές περιέχουν από έναν αριθμό. Τον αριθμό του τμήματος που παρουσίασε βλάβη με φθίνουσα όμως σειρά.

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

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

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

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

#include <stdio.h>
#define exch(A,B) { 
  int t[2]; t[0]=A[0]; t[1]=A[1]; 
  A[0] = B[0]; A[1]=B[1]; 
  B[0] = t[0]; B[1]=t[1]; }

void quicksort(int (*a)[2], int l, int r)
{
  int k, i = l-1, j = r, p = l-1, q = r, v = a[r][1], v0 = a[r][0];
  if (r <= l) return;
  
  while(1)
  {
    while (a[++i][1] > v || (a[i][1] == v && a[i][0] < v0) ) ;
    while (v > a[--j][1] || (a[j][1] == v && a[j][0] > v0)) if (j == l) break;
    if (i >= j) break;
    exch(a[i], a[j]);
  } 

  exch(a[i], a[r]); j = i-1; i = i+1;
  for (k = l; k < p; k++, j--) exch(a[k], a[j]);
  for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
  quicksort(a, l, j);
  quicksort(a, i, r);
}

int main() {
  FILE *in = fopen("hydrogen.in", "r");
  int out_arr[10000][2],i,x,y,in_len,out_len = 0; 

  fscanf(in, "%d", &in_len); 

  for (i = 0; i < in_len; i++)
  {
    fscanf(in,"%d %d",&x,&y);
    if (y==0)
      continue;
    out_arr[out_len][0] = x;
    out_arr[out_len][1] = y;
    out_len++;
  } 

  fclose(in); 

  quicksort(out_arr, 0, out_len-1); 
  FILE *out = fopen("hydrogen.out", "w");
  fprintf(out, "%d\n", out_len);
  for (i = 0; i<out_len; i++)
    fprintf(out, "%d\n", out_arr[i][0]); 

  fclose(out);
  return 0;
}

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

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

using namespace std;

struct at{
  int code,a;
};

bool comp(at a, at b){
  if(a.a==b.a){ return (a.code < b.code); }
  return (a.a > b.a);
}

int main(void){
  FILE *fin=fopen("hydrogen.in","r");
  int n;
  at A;
  vector<at> v;
  fscanf(fin,"%d\n",&n);
  for(int i=0;i<n;++i){
    fscanf(fin,"%d %d\n",&A.code,&A.a);
    if(A.a!=0){
      v.push_back(A);
    }
  }
  fclose(fin);
  sort(v.begin(),v.end(),comp);
  FILE *fout=fopen("hydrogen.out","w");
  n=(int)v.size();
  fprintf(fout,"%d\n",n);
  for(vector<at>::iterator it=v.begin();it!=v.end(); it++)
    fprintf(fout,"%d\n",it->code); 

  fclose(fout);
  return 0;
}     

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

program hydrogen;

type section_errors_diad=record
  section_ID: integer;
  errors: integer;
end;

var f:text;
    c_count: integer;
    i,j,k: integer;
    a: array[1..10000] of section_errors_diad;
    b: section_errors_diad;
    max_a: integer;
    c1,c2,cc,c_errors: integer;

begin
  max_a:=0;
  assign(f,'hydrogen.in');
  reset(f);
  readln(f,c_count);

  for i:=1 to c_count do
  begin
    readln(f,b.section_ID,b.errors);
    if b.errors<>0 then
    begin
      case max_a of           { ***** binary search algorithm ***** }
      0: a[1]:=b;
      1: if b.errors<=a[1].errors then 
           a[2]:=b
         else 
         begin
           a[2]:=a[1];
           a[1]:=b;
         end;
      else
        begin
          if b.errors<=a[max_a].errors then 
            a[max_a+1]:=b
          else if b.errors>=a[1].errors then 
          begin
            for j:=max_a downto 1 do a[j+1]:=a[j];
            a[1]:=b;
          end
          else
          begin
            c1:=1;
            c2:=max_a;
            while c1+1<c2 do
            begin
              cc:=round((c1+c2)/2);
              c_errors:=b.errors-a[cc].errors;
              if c_errors<0 then c1:=cc
              else if c_errors>0 then c2:=cc
              else 
              begin
                c1:=cc;
                c2:=c1+1;
              end;
            end;
            for j:=max_a downto c2 do a[j+1]:=a[j];
            a[c2]:=b;
          end;
        end;
      end;               { **** END of binary search algorithm **** }
      inc(max_a);
    end;
  end;

  close(f);

  c2:=1;
  repeat
    c1:=c2;
    while ((a[c1].errors=a[c2+1].errors) and (c2<max_a)) do inc(c2);
    if c2>c1 then for i:=c1+1 to c2 do
    begin
      j:=c1;
      while ((a[i].section_ID>a[j].section_ID) and (j<i)) do inc(j);
      if j<i then
      begin
        b:=a[i];
        for k:=i downto j+1 do a[k]:=a[k-1];
        a[j]:=b;
      end;
    end;
    inc(c2);
  until c2>max_a;

  assign(f,'hydrogen.out');
  rewrite(f);
  writeln(f,max_a);
 
  for i:=1 to max_a do writeln(f,a[i].section_ID);
  close(f);
end.

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

Πρόβλημα (Γενική Περιγραφή)

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

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

Πρόβλημα (Αναλυτική Περιγραφή)

Στο μοντέλο που ακολουθούμε, δίνεται μία ορθογώνια παραλληλόγραμμη περιοχή μεγέθους Ν x M, όπου Ν και Μ ακέραιοι αριθμοί (1 ≤ N, Μ ≤ 1000).

Η περιοχή χωρίζεται σε ορθογώνια τμήματα εμβαδού 1 x 1, κάθε ένα από τα οποία μπορεί να αναγνωριστεί αρχικά ή ως δασικό ή ως βραχώδες.

Κάθε τμήμα προσδιορίζεται από τις συντεταγμένες της άνω αριστερά (βορειοδυτικής κορυφής του X και Y, όπου Χ και Υ ακέραιοι αριθμοί (1 ≤ Χ ≤ Ν, 1 ≤ Υ ≤ Μ). Χ είναι η οριζόντια συντεταγμένη και Υ η κάθετη. Το τμήμα (1, 1) βρίσκεται στην πάνω αριστερή γωνία του χάρτη.

Η αναγνώριση του τύπου κάθε τμήματος προσδιορίζεται με έναν χαρακτήρα. Με τον χαρακτήρα της τελείας (.) προσδιορίζεται ένα δασικό τμήμα, ενώ με τον χαρακτήρα «παπάκι» (@) προσδιορίζεται ένα βραχώδες.

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

Αν δίνονται οι συντεταγμένες του δασικού τμήματος όπου ξεκίνησε η φωτιά, το πρόγραμμά σας θα πρέπει να υπολογίζει το πλήθος C των δασικών τμημάτων που θα καούν, (υποθέτουμε ότι δεν υπάρχει κατάσβεση), όπου C ακέραιος αριθμός με (1 ≤ C ≤ M*N).

Παρατήρηση: Δεν γίνεται να ξεκινήσει φωτιά σε βραχώδες ή καμένο τμήμα.

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

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

Στην πρώτη γραμμή υπάρχουν οι ακέραιοι Ν και Μ που αντιπροσωπεύουν τις διαστάσεις της περιοχής, χωρισμένοι με ένα κενό.

Στη δεύτερη γραμμή υπάρχουν δύο αριθμοί Ν_f και M_f, οι οποίοι προσδιορίζουν τις συντεταγμένες του δασικού τμήματος όπου ξεκινάει η φωτιά, χωρισμένοι με ένα κενό.

Οι επόμενες Μ γραμμές περιλαμβάνουν από Ν ακριβώς χαρακτήρες έκαστη. Οι χαρακτήρες αυτοί είναι είτε τελεία (.) είτε «παπάκι» (@) συμβολίζοντας ένα δασικό ή ένα βραχώδες τμήμα αντίστοιχα.

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

Το αρχείο εξόδου με όνομα fire.out είναι αρχείο κειμένου με την εξής δομή.

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

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

Στο 1o παράδειγμα η φωτιά ξεκινάει από το δασικό τμήμα στη δεύτερη στήλη και την τρίτη γραμμή. Η φωτιά επεκτείνεται στις δασικές εκτάσεις πάνω, δεξιά, και κάτω από το τμήμα αυτό. Δεν επεκτείνεται όμως στα αριστερά του, επειδή συναντάει βραχώδη τμήματα.

Στο 2o παράδειγμα η φωτιά ξεκινάει από το δασικό τμήμα στην πέμπτη στήλη και την πέμπτη γραμμή και εγκλωβίζεται εκεί, γιατί το τμήμα περιβάλλεται μόνο από βραχώδη τμήματα.

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

• Υποθέτουμε ότι τα αρχεία εισόδου έχουν μόνο τους επιτρεπόμενους χαρακτήρες και ως εκ τούτου δεν απαιτείται κανένας έλεγχος ορθότητας.
• Μέγιστος Χρόνος Εκτέλεσης 1 sec.

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

program Fire;

type
  myint=0..1001;
  ccc=0..1000000;

var
  xx,yy,M,N,i,j:myint;
  C:ccc;
  infile,outfile:text;
  ch:char;
  pin:array[0..1001,0..1001] of boolean;

PROCEDURE burn(x,y:myint);
begin
  if pin[x,y] then
  begin
    pin[x,y]:=false;
    C:=C+1;
    burn(x-1,y);
    burn(x+1,y);
    burn(x,y+1);
    burn(x,y-1);
  end;
end;

BEGIN
  C:=0;
  assign(infile,'fire.in');
  reset(infile);
  readln(infile,N,M);
  readln(infile,xx,yy);
  for i:= 1 to M do
  begin
    for j:= 1 to N do
    begin
      read(infile,ch);
      if ch='@' then
        pin[i,j]:=false
      else
        pin[i,j]:=true;
    end;
    readln(infile);
  end;
  close(infile);

  for j:= 0 to N+1 do
  begin
    pin[0,j]:=false;
    pin[M+1,j]:=false;
  end;
  for i:= 0 to M+1 do
  begin
    pin[i,0]:=false;
    pin[i,N+1]:=false;
  end;

  burn(yy,xx);

  assign(outfile,'fire.out');
  rewrite(outfile);
  writeln(outfile,C);
  close(outfile);
END.

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

#include<stdio.h>
#define ADD(a,b)  if(A[a][b]==1){ \
                    A[a][b]=0;\
                    B[EndB].x = a;\
                    B[EndB].y = b;\
                    EndB++;\
                  } 
 
struct forest 
{ int x, y;} B[1000000];

char T[1001*1000], A[1002][1002];

int main() {
  int N, M, StartB=0, EndB=0, x, y ,i, j, t=0;
  FILE *fin = fopen("fire.in","r");
  FILE *fout = fopen("fire.out","w");
  fscanf(fin,"%d %d %d %d", &M, &N, &y, &x);
  fread(T,sizeof(char),(M+1)*N, fin);
  for(i=1;i<=N;i++) for(t++,j=1;j<=M;j++) A[i][j] = (T[t++]=='.');
  ADD(x,y);
  while(StartB!=EndB){
    x=B[StartB].x;
    y=B[StartB].y;
    ADD(x+1,y);  ADD(x-1,y);
    ADD(x,y+1);  ADD(x,y-1);
    StartB++;
  }
  fprintf(fout,"%d\n", EndB);
  return 0; 
}     

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

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

char a[1000][1000];
int b[1000000][2];
int i,j,N,M,st,gr;
int  C,T,ex;
FILE * fin;
FILE * fout;

int main(){
  int qgr,qst;
  fin = fopen("fire.in" , "r");
  fout = fopen("fire.out" , "w");
  fscanf(fin,"%d %d %d %d",&N,&M,&st,&gr);
  for(i=0;i<=M;i++)
  {
    fscanf(fin,"%s",a[i]);
  }
  fclose(fin);
 
  gr=gr-1;
  st=st-1;
  b[0][0]=gr;
  b[0][1]=st;
  ex=0;
  T=1;
    
  while(ex<T)
  {
    qgr=b[ex][0];
    qst=b[ex][1]; 
    a[qgr][qst]='K';
    if(qgr-1>=0){if(a[qgr-1][qst]=='.')
      { b[T][0]=qgr-1; b[T][1]=qst; a[qgr-1][qst]='K'; T++;}}
    if(qgr+1<=M+1){if(a[qgr+1][qst]=='.')
      { b[T][0]=qgr+1; b[T][1]=qst; a[qgr+1][qst]='K'; T++;}}
    if(qst+1<=N+1){if(a[qgr][qst+1]=='.')
      { b[T][0]=qgr; b[T][1]=qst+1; a[qgr][qst+1]='K'; T++;}}
    if(qst-1>=0){if(a[qgr][qst-1]=='.')
      { b[T][0]=qgr; b[T][1]=qst-1; a[qgr][qst-1]='K'; T++; }}
    ex++; 
  } 

  fprintf(fout,"%d\n" , ex);
  fclose(fout);
  return 0; 
}     

Θέμα B' Φάσης: Πρόβλημα στον «Έξυπνο» Διαδραστικό Πίνακα (Μαθητές Γυμνασίου)

Καθηγητής Πληροφορικής ενός Λυκείου, αντιμετώπισε ένα ξαφνικό πρόβλημα. Ο αφοσιωμένος υπολογιστής που καταγράφει τα κείμενα που εμφανίζονται στον «έξυπνο» ηλεκτρονικό πίνακα του εργαστηρίου Πληροφορικής, του «έδειξε» μπλε οθόνη! Με χρήση ειδικών εργαλείων λογισμικού ανάκτησε σε φυσικό επίπεδο (surface reading) τμήμα των αρχείων του δίσκου, χωρίς όμως τα στοιχεία χρόνου. Έτσι δυστυχώς όλες οι θέσεις που αντιστοιχούσαν στο περιεχόμενο του «έξυπνου» ηλεκτρονικού πίνακα ήταν πλήρεις με χαρακτήρες. (Τους τελευταίους που είχαν αναγραφεί στην κάθε θέση). Για την ανάκτηση των στοιχείων χρόνου, χρειάζεται να βρει τη θέση στη συμβολοσειρά που είναι εγγεγραμμένη στο δίσκο, τουλάχιστον μιας φράσης, που θυμάται ότι είχε γράψει την τελευταία φορά.

Παράδειγμα

Στην ευρύτερη συμβολοσειρά A;KDLJKNF,lMBUBBLE SORTDIHEWN GLM FR &JSALJFLMC, η συμβολοσειρά BUBBLE SORT ξεκινά στη 13η θέση.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα matrix.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή περιέχουν έναν ακέραιο αριθμό Ν (2 ≤ Ν ≤ 1024) τον αριθμό των χαρακτήρων του ζητουμένου κειμένου. Στη δεύτερη γραμμή περιέχεται το αναζητούμενο κείμενο. Στην τρίτη γραμμή περιέχουν έναν ακέραιο αριθμό Μ (8 ≤ Μ ≤ 65536) τον αριθμό των χαρακτήρων του κειμένου μέσα στο οποίο θα γίνει η αναζήτηση. Στην τέταρτη γραμμή υπάρχει το κείμενο μέσα στο οποίο θα γίνει η αναζήτηση.

- Όλοι οι χαρακτήρες έχουν κωδικοποίηση ANSI (ASCII 33 - 254)

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

Τα αρχεία εξόδου με όνομα matrix.out είναι αρχεία κειμένου με την εξής δομή: Περιέχουν ακριβώς έναν ακέραιο αριθμό P (1 ≤ P ≤ 65534). Τον αριθμό, που δείχνει τη θέση στον αρχικό πίνακα, στην οποία εντοπίστηκε η αρχή της ζητούμενης συμβολοσειράς.

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

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

• Αν δεν βρεθεί σε καμία θέση η ζητούμενη συμβολοσειρά, το αρχείο εξόδου θα έχει ως μόνο περιεχόμενο το χαρακτήρα F.
• Τα αρχεία εισόδου έχουν μόνο τους επιτρεπόμενους χαρακτήρες και ως εκ τούτου δεν απαιτείται κανένας έλεγχος ορθότητας.
• N ≤ Μ
• Μέγιστος Χρόνος Εκτέλεσης 1 sec.

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

Program Matrix(Indata, Outdata);
Var
  Indata, Outdata: text;
  j, i, K, N: longint;
  C: char;
  S: array [1..1024] of char;
  T: array [1..65536] of char;
  flag:boolean;

begin
  assign (Indata, 'matrix.in');
  reset (Indata);
  readln (Indata, K);
  for j:=1 to K do
    begin
      read (Indata, C);
      S[j]:=C;
    end;
  readln (Indata);
  readln (Indata, N);
  for i:=1 to N do
    begin
      read (Indata, C);
      T[i]:=C;
    end;
  close (Indata);
  if K=N then
    begin
      flag:=false;
      i:=2; 
      j:=1;
      while (S[j] = T[j]) AND (j<=k) do
        j:=j+1; 
      if j=K+1 then
        flag:=true;
    end
  else
    begin
      flag:=false;
      i:=1;
      while (i <= (N-K)) AND (flag=false) do
        begin
          j:=1;
          while S[j] = T[i+j-1] do
            j:=j+1; 
          if j=K+1 then
            flag:=true; 
          i:=i+1;
        end;
    end;
  assign (Outdata, 'matrix.out');
  rewrite (Outdata);
  if flag=true then
    begin
      i:=i-1;
      writeln (Outdata, i);
    end
  else
    begin
      writeln (Outdata, 'F');
    end;
  close (Outdata);
  halt (0);
end.

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

#include "stdio.h"
#include "stdlib.h"

short i,i2;FILE * in_file;

FILE * out_file;unsigned short in_fn,in_ssn,letternumber=0;

int main()
{
  in_file = fopen ("matrix.in","r");
  out_file = fopen ("matrix.out","w+");
  fscanf(in_file,"%d",&in_fn);
  char stf[in_fn];
  fseek(in_file,1,SEEK_CUR);
  fread (&stf,1,in_fn,in_file); 
  fscanf(in_file,"%d",&in_ssn);
  fseek(in_file,1,SEEK_CUR);
  char sts[in_ssn];
  fread (&sts,1,in_ssn,in_file);
  short ltr,ltr2;
     
  for(i=0;i<in_ssn;i++) 
  {
    ltr=0;
    if(stf[ltr] == sts[i])
    {
      ltr++;
      for(i2=1;i2<in_fn;i2++)
      {
        ltr2 = ltr;
        if(stf[ltr] == sts[i+i2])
        {
          ltr++;
        } 
        if(ltr==in_fn)
        {
          letternumber=i+1;
          fprintf(out_file,"%d\n",letternumber);
          fclose(in_file);
          fclose(out_file);
          return 0;
        }
        if(ltr2 == ltr)
        { 
          break;
        }
      }
    } 
  }
  fprintf(out_file,"F\n",letternumber); 
       
  fclose(in_file);
  fclose(out_file);
  return 0;
}

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

#include <stdio.h>
     
int TimesFound[257], PosFound[257][1025], N; 
long int M; 
unsigned char str[65540],pat[1025]; 

int Allign(unsigned char c, int x) 
{ 
  long int f=TimesFound[c], t; 
     
  if(f<x) return -1; 
  t=PosFound[c][x-1]; 
  return t; 
} 

int Compare(long int s, long int e) 
{ 
  long int i,j; 
  j=0; 
  for(i=s;i<e;i++) 
  { 
    if(pat[j++]!=str[i]) return -1; 
  } 
  return 0; 
} 
     
int main() 
{ 
  FILE *fin, *fout; 
  long int i,j,start,end,allign,found=-1; 
  unsigned char c; 
     
  for(i=0;i<256;i++) TimesFound[i]=0; 
     
  fin = fopen("matrix.in","r"); 
  fout = fopen("matrix.out","w"); 
     
  fscanf(fin,"%d\n",&N); 
  for(i=0;i<N;i++) 
  { 
    fscanf(fin,"%c",&c); 
    pat[i]=c; 
    PosFound[c][TimesFound[c]]=i; 
    TimesFound[c]++; 
  } 
     
  fscanf(fin,"\n%ld\n",&M); 
  for(i=0;i<M;i++) 
  { 
    fscanf(fin,"%c",&str[i]); 
  } 
     
  start=0; 
  end=N-1; 
     
  while(found==-1) 
  { 
    j=1; 
    allign=-2; 
    while(allign!=-1 && found==-1) 
    { 
      allign=Allign(str[end],j++); 
      if(allign!=-1) 
        if(Compare(end-allign,end-allign+N)==0) 
        { 
          found=end-allign; 
        } 
    } 
    start+=N; 
    end+=N; 
    if(end>M && found<0) found=-2; 
  } 
     
  if(found<0) fprintf(fout,"F\n"); 
  else fprintf(fout,"%ld\n",found+1); 
     
  fclose(fin); 
  fclose(fout); 
  return 0; 
}     

Θέμα 1o Τελικής Φάσης: Lines man

Το ποδόσφαιρο από την ανακάλυψή του στο Πανεπιστήμιο του Cambridge, έγινε το πιο δημοφιλές αλλά και το πιο εύκολα παιζόμενο άθλημα. Ένας σχετικά επίπεδος τόπος και μια μπάλα αρκούν. Σύμφωνα με τους κανόνες του, ο διαιτητής κινείται μέσα στο γήπεδο και οι επόπτες γραμμών κατά μήκος των πλευρικών γραμμών, στο μισό γηπέδου έκαστος. Αν το γήπεδο ποδοσφαίρου έχει μήκος Α, οι δύο επόπτες γραμμών ξεκινούν από το κέντρο του γηπέδου (A/2). Μέσα στο γήπεδο η μπάλα κινείται σε διάφορα σημεία. Οι επόπτες πρέπει να παρακολουθούν τις φάσεις, κινούμενοι μόνο κατά μήκος των πλευρικών γραμμών από το 0 έως Α/2 και από Α/2 έως Α αντίστοιχα.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα lines_man.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν άρτιο ακέραιο αριθμό Α (10 ≤ Α ≤ 1.000): το μήκος του γηπέδου. Στη δεύτερη γραμμή έχουν έναν ακέραιο αριθμό Μ (10 ≤ Μ ≤ 100.000): το πλήθος των φάσεων. Οι επόμενες Μ γραμμές περιέχουν από ένα ακέραιο αριθμό Υ (0 ≤ Υ ≤ Α): το μήκος του γηπέδου επί του οποίου εξελίσσεται η αντίστοιχη φάση.

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

Τα αρχεία εξόδου με το όνομα lines_man.out είναι αρχεία κειμένου με την εξής δομή. Έχουν μία γραμμή με ακριβώς δύο αριθμούς, L1 και L2 (0 ≤ L1, L2 ≤ 10.000.000): τη συνολική απόσταση που διέτρεξε κάθε επόπτης γραμμών. Ο πρώτος κινείται από 0 έως A/2 και ο δεύτερος κινείται από Α/2 έως Α.

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

Εξήγηση παραδείγματος:

Το μήκος του γηπέδου είναι 100, άρα ο πρώτος επόπτης κινείται μεταξύ 0 και 50 και ο δεύτερος μεταξύ 50 και 100 (βλ. σχήμα). Γίνονται συνολικά 10 φάσεις. Και οι δύο επόπτες ξεκινούν από τη θέση 50. Στις πρώτες τέσσερις φάσεις (49, 30, 25 και 0) ο πρώτος επόπτης τρέχει μέχρι τη θέση 0 διανύοντας συνολικά 50 μέτρα, ενώ ο δεύτερος επόπτης παραμένει ακίνητος στη θέση 50. Στην πέμπτη φάση (50), ο πρώτος επόπτης επιστρέφει στη θέση 50 διανύοντας άλλα 50 μέτρα και ο δεύτερος παραμένει ακίνητος στη θέση 50. Στην έκτη φάση (55), ο δεύτερος επόπτης τρέχει μέχρι τη θέση 55 διανύοντας 5 μέτρα, ενώ ο πρώτος παραμένει ακίνητος στη θέση 50. Στην έβδομη φάση (40), ο δεύτερος επόπτης επιστρέφει στη θέση 50 διανύοντας άλλα 5 μέτρα και ο πρώτος επόπτης τρέχει μέχρι τη θέση 40 διανύοντας 10 μέτρα. Στις τελευταίες τρεις φάσεις (30, 20 και 0), ο πρώτος επόπτης τρέχει μέχρι τη θέση 0 διανύοντας συνολικά 40 μέτρα ενώ ο δεύτερος επόπτης παραμένει ακίνητος στη θέση 50. Οι συνολικές αποστάσεις που διανύθηκαν από τους δύο επόπτες είναι: L1 = 50+50+10+40 = 150 και L2 = 5+5 = 10.

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

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

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

#include <fstream>
#include <vector>

using namespace std;

int abs (int n) {
  return (n >= 0?n:n * -1);
}

int main() {
  ifstream in("lines_man.in");
  ofstream out("lines_man.out");
  int A;
  in >> A;
  int M; 
  in >> M;
  int firstdude = 0, seconddude = 0;
  int firstdudepos = A / 2, seconddudepos = A / 2;
  for (int i = 0; i < M; i++) {
    int x;
    in >> x;
    if (x <= firstdudepos || x >= firstdudepos && x <= A/2) {
      firstdude += abs(firstdudepos - x);
      firstdudepos = x;
    }
    else {
      firstdude += abs (firstdudepos - A/2);
      firstdudepos = A/2;
    }
    if (x >= seconddudepos || x <= seconddudepos && x >= A/2) {
      seconddude += abs(seconddudepos - x);
      seconddudepos = x;
    }
    else {
      seconddude += abs (seconddudepos - A/2);
      seconddudepos = A/2;
    }
  }
  out << firstdude << " " << seconddude << endl;
  return 0;
}     

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

Το Δίκτυο των Ελληνικών Πανεπιστημίων και Α-ΤΕΙ (http://www.gunet.gr) έχει αναπτύξει μια συστοιχία (cluster) από N web servers. Κάθε server:

• διαχειρίζεται τις ίδιες M σελίδες,
• κρατάει ένα μετρητή για κάθε σελίδα, που αυξάνει κατά 1 όταν ζητηθεί η σελίδα αυτή από τον server, και
• κρατάει τις τιμές αυτών των μετρητών ταξινομημένες σε φθίνουσα σειρά.

Πρόβλημα

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

Παράδειγμα

Για Ν=5 servers και Μ=5 σελίδες

Επεξήγηση: Οι σελίδες έχουν αριθμηθεί από 0 έως Μ-1. Στο server S1 η σελίδα 3 έχει ζητηθεί 99 φορές, η 1 66, η 0 63 κοκ. Συνολικά τα αιτήματα που υποβλήθηκαν για τις 5 σελίδες ήταν:

Για Κ=2, οι δύο δημοφιλέστερες σελίδες είναι η 3 και η 1.

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

Τα αρχεία εισόδου με όνομα servers.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν τρεις αριθμούς M, Ν, K. Τον αριθμό Μ των φιλοξενούμενων σελίδων (5 ≤ Μ ≤ 10.000). Σημειώνεται ότι η πρώτη σελίδα αριθμείται με 0 . Τον αριθμό N των servers (5 ≤ Ν ≤ 1.000). Τον αριθμό Κ των δημοφιλέστερων σελίδων που ζητούνται (2 ≤ Κ ≤ Μ). Οι αριθμοί ξεχωρίζουν μεταξύ τους με ένα κενό. Στις επόμενες M γραμμές υπάρχουν N ζεύγη ακεραίων. Η πρώτη γραμμή έχει για κάθε server τη σελίδα που ζητήθηκε περισσότερο, η δεύτερη την αμέσως επόμενη, κ.ο.κ. Σε κάθε ζεύγος, ο πρώτος ακέραιος είναι ο αριθμός της σελίδας και ο δεύτερος πόσες φορές αυτή ζητήθηκε. Όλοι οι αριθμοί ξεχωρίζουν μεταξύ τους με ένα κενό. Καμία σελίδα δε θα έχει ζητηθεί από κάποιον server περισσότερες από 500.000 φορές.

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

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

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

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

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

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

#include <fstream>
#include <iostream>
#include <stdlib.h>

using namespace std;

struct site
{
  int id;
  long int hits;
};

int compare(const void *a, const void *b)
{
  site sa;
  site sb;
  sa = *(site*)a;
  sb = *(site*)b;
  return sb.hits-sa.hits;
}

int main()
{
  ifstream fin("servers.in");
  ofstream fout("servers.out");
  int M, N, K, i, s, j;
  long int h;
  site sites[10000];
  fin >> M >> N >> K;
  for(i=0;i<M;i++)
  {
    sites[i].id=i;
    sites[i].hits=0;
  }
  for(i=0;i<M;i++)
  {
    for(j=0;j<N;j++)
    {
      fin >> s >> h;
      sites[s].hits+=h;
      sites[s].hits << endl;
    }
  }
  qsort(sites,M,sizeof(site),compare);
  for(i=0;i<K;i++)
  {
    fout << sites[i].id << ' ' << sites[i].hits << '\n';
  }
  fin.close();
  fout.close();
  return 0;
}     

Θέμα 3o Τελικής Φάσης: Get out!

Ένα τετράγωνος χώρος στάθμευσης (parking) αυτοκινήτων έχει μήκος πλευράς Ν μέτρα. Σε αυτόν βρίσκονται σταθμευμένα αυτοκίνητα διαστάσεων 2x1 μέτρα. Τα αυτοκίνητα είναι σταθμευμένα παράλληλα προς τις πλευρές του τετραγώνου και σε ακέραιες συντεταγμένες, άλλα οριζόντια (κατά μήκος σειρών) και άλλα κάθετα (κατά μήκος στηλών). Κάθε αυτοκίνητο μπορεί να μετακινείται μόνο κατά μήκος του άξονά του και μέσα στο τετράγωνο, εφόσον δεν εμποδίζεται από άλλο αυτοκίνητο, και δεν μπορεί να περιστρέφεται.

Η εταιρεία παροχής φυσικού αερίου θέλει να σκάψει κατά μήκος μίας οριζόντιας γραμμής (σειράς) στη θέση R μέσα στο χώρο στάθμευσης, για να περάσει έναν υπόγειο αγωγό. Για το σκοπό αυτό πρέπει να μετακινηθούν τα αυτοκίνητα που βρίσκονται πάνω σε αυτή τη σειρά.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα getout.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν δύο ακέραιους αριθμούς: το μήκος Ν της πλευράς του τετραγώνου (4 ≤ Ν ≤ 8) και τη θέση R της σειράς όπου θα τοποθετηθεί ο αγωγός (1 ≤ R ≤ Ν). Οι επόμενες N γραμμές περιγράφουν τα αυτοκίνητα που είναι σταθμευμένα οριζόντια, κατά μήκος των σειρών του τετραγώνου. Κάθε γραμμή αρχίζει με το πλήθος Xi των αυτοκινήτων που είναι σταθμευμένα κατά μήκος αυτής της σειράς, ακολουθούμενο από Xi ακέραιους αριθμούς: τις συντεταγμένες όπου βρίσκονται τα αυτοκίνητα κατά μήκος της σειράς. (Οι συντεταγμένες είναι μεταξύ 1 και N. Ένα αυτοκίνητο οριζόντια σταθμευμένο με συντεταγμένη 5 βρίσκεται πάνω στις στήλες 5 και 6 του τετραγώνου.) Ομοίως, οι επόμενες N γραμμές περιγράφουν τα αυτοκίνητα που είναι τοποθετημένα κάθετα, κατά μήκος των στηλών του τετραγώνου.

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

Τα αρχεία εξόδου με το όνομα getout.out είναι αρχεία κειμένου με μόνο μία γραμμή που περιέχει μόνο έναν αριθμό: το ελάχιστο πλήθος κινήσεων. Αν δεν είναι δυνατόν να ελευθερωθεί η σειρά R για να τοποθετηθεί ο αγωγός, το αποτέλεσμα θα είναι –1.

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

Εξήγηση παραδείγματος

Για να ελευθερωθεί η σειρά 4 του τετραγώνου, αρκεί να μετακινηθεί το αυτοκίνητο Δ δύο θέσεις κάτω, μετά το Ζ μία θέση κάτω, μετά το Γ μία θέση αριστερά, και τέλος το Ε δύο θέσεις κάτω. Χρειάζονται επομένως 4 κινήσεις.

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

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

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

#include <cstdio>
#include <set>
#include <queue>
#include <cstdlib>

using namespace std;

int n, r;
FILE *fin, *fout;

struct state {
  char park[9][9];
  int moves;

  bool operator==(const state &b) const {
    int i, j;
    for (i=1; i<=n; i++) 
      for (j=1; j<=n; j++) 
        if (park[i][j]!=b.park[i][j]) return false;
    return true;
  }

  bool operator<(const state &b) const {
    int i, j;
    for (i=1; i<=n; i++) 
      for (j=1; j<=n; j++)
        if (park[i][j]<b.park[i][j]) return true;
        else if (park[i][j]>b.park[i][j]) return false;
    return false;
  }
  
  void operator=(const state &b) {
    int i, j;
    for (i=1; i<=n; i++) 
      for (j=1; j<=n; j++) 
        park[i][j] =  b.park[i][j];
    moves = b.moves;
  }
};

set<state> s;
queue<state> q;
char dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void print(state &tmp) {
  for (int i=n; i>=1; i--) {
    for (int j=1; j<=n; j++)
      printf("%d ", tmp.park[i][j]);
    printf("\n");
  } 
  printf("\n");
}

void check(state &tmp) {
  int i;
  for (i=1; i<=n; i++) 
    if (tmp.park[r][i]!=0) return;
  fprintf(fout, "%d\n", tmp.moves);
  exit(0);
}

int main() {
  fin=fopen("getout.in", "r");
  fout=fopen("getout.out", "w");
  state init, tmp, buk;
  int d=1, i ,j, t, x, y, k, z;
  fscanf(fin, "%d %d", &n, &r);
  for (i=1; i<=n; i++) 
    for (j=1; j<=n; j++) 
      init.park[i][j] = 0;
  for (i=1; i<=n; i++) {
    fscanf(fin, "%d", &t);
    if (i==r && t!=0) { fprintf(fout, "-1\n"); return 0; }
    for (j=1; j<=t; j++) { 
      fscanf(fin, "%d", &y);
      init.park[i][y] = d; 
      init.park[i][y+1] = d++; 
    }
  }
  for (i=1; i<=n; i++) {
    fscanf(fin, "%d", &t);
    for (j=1; j<=t; j++) { 
      fscanf(fin, "%d", &x);
      init.park[x][i] = d; 
      init.park[x+1][i] = d++; 
    }
  }
  init.moves = 0;
  s.insert(init);
  q.push(init);
  check(init);
  while (!q.empty()) {
    char used[100]={0};
    tmp = q.front();
    q.pop();
    tmp.moves++;
    buk = tmp;
    for (i=1; i<=n; i++)
      for (j=1; j<=n; j++) {
        if (tmp.park[i][j]) {
          for (k=0; k<4; k++) {
            x = i + dir[k][0]; 
            y = j + dir[k][1];
            if (i>=1 && i<=n && j>=1 && j<=n
              && tmp.park[i][j]==tmp.park[x][y] 
              && !used[tmp.park[i][j]]) break;
          }
        if (k!=4) {
          used[tmp.park[i][j]] = 1;
          if (i==x) {
            k = j;
            for (z=k-1; z>=1; z--) {
              if (!tmp.park[i][z]) {
                tmp.park[i][z] = tmp.park[i][z+1];
                tmp.park[i][z+2] = 0;
              } 
              else break;
              if (s.find(tmp)==s.end()) {
                q.push(tmp); 
                s.insert(tmp); 
                check(tmp);
              }
            }
            tmp = buk;
            for (z=k+2; z<=n; z++) {
              if (!tmp.park[i][z]) {
                tmp.park[i][z] = tmp.park[i][z-2];
                tmp.park[i][z-2] = 0;
              } 
              else break;
              if (s.find(tmp)==s.end()) {
                q.push(tmp); 
                s.insert(tmp); 
                check(tmp);
              }
            }
            tmp = buk;
          } 
          else {
            k = i;
            for (z=k-1; z>=1; z--) {
              if (!tmp.park[z][j]) {
                tmp.park[z][j] = tmp.park[z+1][j];
                tmp.park[z+2][j] = 0;
              } 
              else break;
              if (s.find(tmp)==s.end()) {
                q.push(tmp); 
                s.insert(tmp); 
                check(tmp);
              }
            }
            tmp = buk;
            for (z=k+2; z<=n; z++) {
              if (!tmp.park[z][j]) {
                tmp.park[z][j] = tmp.park[z-2][j];
                tmp.park[z-2][j] = 0;
              } 
              else break;
              if (s.find(tmp)==s.end()) {
                q.push(tmp); 
                s.insert(tmp); 
                check(tmp);}
              }
              tmp = buk;
            }
          }
        }
      }
    }
  fprintf(fout, "-1\n");
  return 0;
}