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

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

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

Θέμα Α' Φάσης: Πατρόκλεια Τείχη

Ο αρχαίος Ελληνισμός από τη Μυκηναϊκή περίοδο, ανέπτυξε σημαντικές πόλεις γύρω από τον Αργοσαρωνικό κόλπο. Σε στρατηγικά σημεία του κόλπου (κοιτίδα του αρχαίου Ελληνικού πολιτισμού) κατασκευάστηκαν σημαντικά οχυρά. Στην ανατολική είσοδο του κόλπου, εκεί που ο Αιγαίας με το θάνατό του ονομάτισε για πάνω από 3500 χρόνια το Ελληνικό αρχιπέλαγος, οι αρχαίοι Έλληνες κατασκεύασαν ένα απόρθητο ναυτικό οχυρό. Τα «Πατρόκλεια» τείχη προστάτευαν για αιώνες τον αντίστοιχο ναύσταθμο. Ο Πάτροκλος (απόγονος του Θησέα) με τη βοήθεια των Ατρειδών, χρησιμοποίησαν τεράστιους κυβόλιθους προκειμένου να ορθώσουν την οχύρωση. Ο μύθος λέει ότι ο θεός Απόλλων βοήθησε στη σχεδίαση των τειχών.

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

Αρχεία Εισόδου. Τα αρχεία εισόδου με όνομα patroclos.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει δύο ακέραιους αριθμούς. Τον αριθμό Σ, 100 ≤ Σ < 10000 που εκφράζει την επιφάνεια σε τετραγωνικές μονάδες που πρέπει να έχουν τα τείχη και τον αριθμό N, 10 ≤ N < 1000 που εκφράζει τον αριθμό των κυβόλιθων που μπορούν να χρησιμοποιηθούν. Οι επόμενες Ν γραμμές (2, 3, …, Ν+1) περιέχουν την επιφάνεια των κυβόλιθων, που εκφράζεται με έναν ακέραιο αριθμό Ε, 1 < Ε ≤ 900.

Αρχεία Εξόδου. Τα αρχεία εξόδου με όνομα patroclos.out είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή δίνεται ο ακέραιος Κ, 2 ≤ Κ < 1000, που εκφράζει τον αριθμό των κυβόλιθων που χρησιμοποιήθηκαν. Οι επόμενες Κ γραμμές περιέχουν από έναν ακέραιο αριθμό Μ, 1 ≤ Μ ≤ Ν, που αντιστοιχούν στον αύξοντα αριθμό του κυβόλιθου που χρησιμοποιήθηκε, με φθίνουσα σειρά μεγέθους.

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

Υπόδειξη

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

1. Η τελική επιφάνεια δε μπορεί να είναι σε καμία περίπτωση μεγαλύτερη από τη ζητούμενη. Μπορεί δηλαδή να είναι μικρότερη ή ίση. (Για ζητούμενη π.χ. επιφάνεια 100, η λύση 101 δεν αποδεκτή ακόμα και αν είναι η εγγύτερη δυνατή).
2. Λύσεις που επιτυγχάνουν την πλησιέστερη δυνατή επιφάνεια θα θεωρούνται βέλτιστες ανεξάρτητα από τον αριθμό των κυβόλιθων που χρησιμοποιούν.
3. Θα αξιολογηθούν θετικά, με μικρότερο όμως συντελεστή και προσεγγιστικές λύσεις του προβλήματος (λύσεις δηλαδή που δεν επιτυγχάνουν ακριβώς την πλησιέστερη δυνατή επιφάνεια).

Παράδειγμα. Στον παρακάτω πίνακα έχουμε τέσσερις ισοδύναμες βέλτιστες λύσεις (τρεις με 6 κυβόλιθους και μία με 7):

Και στις τέσσερις περιπτώσεις έχουμε άθροισμα 100 με 6, 6, 6 και 7 κυβόλιθους αντίστοιχα. Μια προσεγγιστική λύση είναι η εξής: Διαδοχικά, προσθέτουμε τους μεγαλύτερους κυβόλιθους που χωράνε κάθε φορά (απλή λύση):

Στην περίπτωση αυτή έχουμε άθροισμα 99 (40+22+20+11+6) με 5 κυβόλιθους.

Μαθητές που θα υποβάλλουν προσεγγιστικές λύσεις όπως η προηγούμενη, θα λάβουν τουλάχιστον το 50% της αντίστοιχης βαθμολογίας και φυσικά θα εξασφαλίσουν τη συμμετοχή τους στη Β΄ φάση. Μαθητές που θα υποβάλλουν βέλτιστη λύση θα λάβουν τη μέγιστη βαθμολογία.

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

/* Ενδεικτική λύση από τον Γιώργο Μπιτζέ */

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

int S, N, stones[1100];

typedef struct states states;
struct states
{
  int pt; //possible total
  int stones[1300];
  int stoneCount;
};

states V[10100];


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


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

  fscanf(in, "%d %d", &S, &N); 

  for(i = 1; i <= N; i++)
    fscanf(in, "%d", &stones[i]); 

  fclose(in); 

  for(i = 1; i <= N; i++)
    for(w = S; w >= stones[i]; w--)
      if(w >= stones[i] && V[w-stones[i]].pt + stones[i] > V[w].pt)
      {
        V[w].stoneCount = V[w-stones[i]].stoneCount;
        V[w].pt = V[w-stones[i]].pt; 

        for(k = 1; k <= V[w].stoneCount; k++)
          V[w].stones[k] = V[w-stones[i]].stones[k];

        V[w].pt += stones[i]; 

        V[w].stoneCount++;
        V[w].stones[V[w].stoneCount] = i;
      } 

  qsort(V[S].stones+1, V[S].stoneCount, sizeof(int), compare);

  fprintf(out, "%d\n", V[S].stoneCount);
  for(i = 1; i <= V[S].stoneCount; i++)
    fprintf(out, "%d\n", V[S].stones[i]); 

  fclose(out);

  return 0;
}

Θέμα Β' Φάσης: Κυκλαδικές Διαδρομές

Ο Μίλτος το δελφίνι και η παρέα του, ζουν στα πανέμορφα νησιά των Κυκλάδων όπως η Θήρα, η Μήλος, η Δήλος, η Σίκινος και η Αμοργός. Κάθε δελφίνι θέλει να βρίσκεται όσο το δυνατόν περισσότερο κοντά στο νησί που γεννήθηκε, αλλά και να μπορεί να επισκέπτεται τους φίλους του στα γύρω νησιά. Τα δελφίνια δυστυχώς δυσκολεύονται να βρίσκουν πάντοτε το δρόμο τους ανάμεσα στα νησιά, και μερικές φορές χάνονται όταν κολυμπούν ανάμεσα σε αυτά με κακοκαιρία. Για αυτό, αποφάσισαν να «χαράξουν» διαδρομές ανάμεσα στα νησιά, τοποθετώντας βότσαλα στο βυθό της θάλασσας. Κάθε διαδρομή συνδέει δύο διαφορετικά νησιά. Για κάθε μέτρο διαδρομής τοποθετούν τέσσερα βότσαλα. (Δηλαδή για να χαράξουν μία διαδρομή ενός χιλιομέτρου χρειάζονται 4000 βότσαλα). Επειδή επιπλέον είναι δύσκολο να συλλεγούν βότσαλα με φωτεινά χρώματα για να ξεχωρίζουν από τα υπόλοιπα, τα δελφίνια θέλουν να χρησιμοποιήσουν όσο το δυνατόν λιγότερα βότσαλα για να χαράξουν τις διαδρομές τους. Ακόμη τα δελφίνια θέλουν να υπάρχουν διαδρομές χαραγμένες από κάθε νησί προς κάθε άλλο, για να μπορούν όλα τα δελφίνια να επισκέπτονται τους φίλους τους. Με τη “χάραξη” αυτών των βοτσαλένιων διαδρομών, κάποια νησιά “συνδέονται” με άλλα απ’ ευθείας, ενώ άλλα συνδέονται μέσω ενός ή περισσότερων ενδιάμεσων νησιών. Για παράδειγμα, η Θήρα και η Αμοργός συνδέονται με μία διαδρομή, ενώ για να πάει κάποιο δελφίνι από τη Σίκινο στη Δήλο θα πρέπει ενδιάμεσα να περάσει από τη Μήλο, έτσι ώστε ο συνολικός αριθμός βότσαλων που θα χρησιμοποιηθεί στις διαδρομές να είναι ελάχιστος.

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

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

Παραδείγματα

Αρχεία εισόδου. Τα αρχεία εισόδου με όνομα cyclades.in στην πρώτη γραμμή έχουν δύο ακέραιους: Τον ακέραιο Ν με 1 ≤ Ν ≤ 1000, ο αριθμός των νησιών που θέλουμε να συνδέσουμε, και τον Μ με 1 ≤ Μ ≤ 500000, ο αριθμός διαδρομών που ακολουθούν ανάμεσα σε νησιά και στις οποίες δεν επικρατούν καταστροφικά ρεύματα. Κάθε μία από τις επόμενες Μ γραμμές περιέχει 3 ακέραιους Α, Β, και Κ (1 ≤ Α < Β ≤ Ν, 1 ≤ Κ ≤ 1000000) όπου Α και Β είναι δύο νησιά ανάμεσα στα οποία μπορούμε να φτιάξουμε διαδρομή και Κ η μεταξύ τους απόσταση σε μέτρα. Η κάθε απόσταση αναφέρεται μία φορά, και προφανώς αν επιτρέπεται κάποια διαδρομή από το Α στο Β θα επιτρέπεται και η ίδια διαδρομή από το Β στο Α.

Αρχεία εξόδου. Τα αρχεία εξόδου με όνομα cyclades.out περιέχουν ακριβώς μία γραμμή με έναν ακέραιο Λ, τον ελάχιστο αριθμό συνολικών βότσαλων που θα πρέπει να συλλέξουν τα δελφίνια για να κατασκευάσουν τις διαδρομές ανάμεσα σε όλα τα νησιά, ή -1 αν δεν υπάρχει καμία πιθανή κατασκευή που να συνδέει μεταξύ τους όλα τα νησιά.

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

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

Στο παράδειγμα οι επισκέψιμες διαδρομές δίνονται από το παρακάτω σχήμα:

Για να χρησιμοποιήσουν τα λιγότερα βότσαλα τα δελφίνια πρέπει να επιλέξουν να επισημάνουν τις διαδρομές: 1-4, 2-6, 3-4, 3-6, 4-5.

Το συνολικό μήκος των παραπάνω διαδρομών είναι (12+2+9+14+14) = 51 μέτρα ή (12+2+9+14+14)*4 = 51*4 = 204 βότσαλα. Κάθε άλλη λύση απαιτεί περισσότερα βότσαλα. Η παραπάνω λύση επιτρέπει όλες τις δυνατές επισκέψεις για παράδειγμα τα δελφίνια μπορούν να πάνε από το νησί 1 στο 2 μέσω της διαδρομής 1-4-3-6-2.

Περιορισμοί

Χρόνος εκτέλεσης: 10 sec
Μέγιστη απαίτηση μνήμης: 32 MB

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

/* Ενδεικτική λύση από τον Γιώργο Μπιτζέ */

#include <stdio.h>

int matrix[1100][1100], N;


void readFile(void)
{
  int M, i, a, b, k; 
  
  FILE *in = fopen("cyclades.in", "r");
  fscanf(in, "%d %d", &N, &M);
  //we do not yet know which nodes connect,
  //so set the weights between all to infinity for now
  //so, when we get the input matrix[i][j] will contain the distance 
  //between i and j if they connect and 999999999 if they don't.
  for(i = 1; i <= N; i++)
    for(a = 1; a <= N; a++)
      matrix[i][a] = 999999999; 
      
  for(i = 1; i <= M; i++)
  {
    fscanf(in, "%d %d %d", &a, &b, &k);
    matrix[a][b] = k;
    matrix[b][a] = k;
  }
  fclose(in);
}


void output(unsigned long long val)
{
  FILE *out = fopen("cyclades.out", "w");
     
  if(val == 0)
    fprintf(out, "%d\n", -1);
  else
    fprintf(out, "%llu\n", val*4);
  fclose(out);
}


void prim(void)
{
  unsigned long long distance[1100], treeCost = 0, minD;
  int inTree[1100], treeSize = 1, i, n; 
  
  //set node1 to be in MST
  for(i = 1; i <= N; i++)
  {
    distance[i] = matrix[1][i];
    inTree[i] = 0;
  } 
  
  inTree[1] = 1; 
  
  while(treeSize < N)
  {
    minD = 999999999, n = -1;
    for(i = 1; i <= N; i++)
      if(distance[i] < minD && inTree[i] == 0)
      {
        minD = distance[i];
        n = i;
      }
      
    if(minD == 999999999 || n == -1)
    { //there is no possible set of vertices 
      //that connect all nodes...
      output(0);
      return;
    } 
    
    treeSize++;
    treeCost += distance[n];
    inTree[n] = 1; 
    
    for(i = 1; i <= N; i++)
      if(distance[i] > matrix[n][i])
        distance[i] = matrix[n][i];
  } 
  
  output(treeCost);
}


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

1ο Θέμα Τελικής Φάσης: Εργαστήριο Κβαντικών Υπολογιστών Παν/μίου Αθηνών

Οι κβαντικοί υπολογιστές λειτουργούν στο επίπεδο των υποατομικών σωματιδίων, όπου ένα κβαντικό δυαδικό ψηφίο μπορεί να θεωρηθεί ότι αντιπροσωπεύει το 1 και το 0 ταυτόχρονα! Κατά τη μέτρηση όμως ή την παρατήρηση, αίρεται η 'ασάφεια'. Για αυτό, ένας κβαντικός υπολογιστής μπορεί θεωρητικά να κάνει πολλές πράξεις ταυτόχρονα. Οι κβαντικοί υπολογιστές χρησιμοποιούν ιδιότητες όπως η μαγνητική ιδιοπεριστροφή (spin) των ατομικών πυρήνων για να αντιπροσωπεύσουν τα κβαντικά δυαδικά ψηφία, ή όπως λέγονται "qubits”. Για την ενταμίευση qubits χρησιμοποιούνται κυρίως οργανικές ενώσεις σε κατάλληλες υποδοχές. Με τη βοήθεια τέτοιων ενώσεων, μπορούμε να δημιουργήσουμε συστάδες qubits με μέγεθος από μερικά μέχρι μερικές δεκάδες qubits.

Στο Εργαστήριο Κβαντικών Υπολογιστών του Πανεπιστημίου Αθηνών, οι πειραματικοί υπολογιστές διαθέτουν τρεις υποδοχές qubits (Α, Β, C). Για να μεταφερθεί ένα σύνολο συστάδων qubit από το Α στο C θα πρέπει: Να μεταφέρεται πρώτα η συστάδα με το μεγαλύτερο μέγεθος και μετά αυτή με το μικρότερο. Μπορεί να γίνει μόνο μια μεταφορά μίας συστάδας κάθε φορά και μόνο μέσω των τριών υποδοχών.

Παράδειγμα με 2 qubits:

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

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

Το αρχείο qubits.in έχει ακριβώς έναν ακέραιο αριθμό που δηλώνει τον αριθμό Ν των συστάδων qubits που περιέχει, όπου 3 ≤ Ν ≤ 20.

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

Το αρχείο qubits.out έχει ανά γραμμή ζεύγη χαρακτήρων Α Β, Α C, B C, B A, C A, C B με κενό μεταξύ τους που εκφράζουν τις μετακινήσεις qubits μεταξύ των υποδοχών.

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

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

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

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

Πρόκειται για έναν κλασσικό αλγόριθμο γνωστό ως Αλγόριθμο του Ανόι (Hanoi). Υλοποιείται με τυπικό κώδικα αρκετών γραμμών ή σε λίγες γραμμές με αναδρομή. Αποτελεί κλασσικό παράδειγμα διδασκαλίας της χρησιμότητας της Αναδρομής. Σχολικό Βιβλίο Γ΄ Ε.Λ. Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον (ΕΠΥ), Τετράδιο Μαθητή, σελ 104. (Υλοποίηση Pascal σελ. 106)

program qubits (Indata, Outdata);
const
  st1='A';
  st2='B';
  st3='C';
var
  n: integer;
  Indata, Outdata: text;


procedure move (n:integer; sta, stb, stc:char);
begin
  if n=1 then
  begin
    writeln (Outdata, sta, ' ', stc);
  end
  else
  begin
    move (n-1, sta, stc, stb);
    writeln (Outdata, sta, ' ', stc);
    move (n-1, stb, sta, stc);
  end;
end;


begin
  assign (Indata, 'qubits.in');
  reset (Indata);
  readln (Indata, n);
  close (Indata);
  assign (Outdata, 'qubits.out');
  rewrite (Outdata);
  move (n, st1, st2, st3);
  close (Outdata);
  halt (0);
end.

2ο Θέμα Τελικής Φάσης: Μπάλες Υάλου

Η εταιρεία “γιούλα” κατασκευάζει γυάλινες μπάλες από ειδικό γυαλί. Κάθε μέρα παράγει ένα σύνολο από μπάλες ίδιας αντοχής. Ωστόσο, διαφορετικά σύνολα μπορεί να έχουν διαφορετική αντοχή. Για να μετρήσει την αντοχή κάθε συνόλου, ο μηχανικός παραγωγής ακολουθεί την εξής διαδικασία: Αφήνει σε ελεύθερη πτώση κάποιες μπάλες (από ένα σύνολο) από διαφορετικά επίπεδα ενός κτιρίου και, επομένως, παριστάνει την αντοχή τους με το χαμηλότερο επίπεδο στο οποίο η μπάλα θα σπάσει στην ελεύθερη πτώση. Κάθε επίπεδο καθορίζεται από ένα όροφο.

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

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

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

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

Το αρχείο balls.in έχει στην πρώτη γραμμή έναν ακέραιο L (όπου 2 ≤ L ≤ 10 ) που παριστάνει το πλήθος των συνόλων που θα ελεγχθούν. Κάθε μια από τις L γραμμές που ακολουθούν περιέχει δύο ακέραιους N, M (όπου 1 ≤ M ≤ N ≤ 500 ) που αντιπροσωπεύουν τα επίπεδα του κτιρίου (χωρίς το ισόγειο) και την αντοχή της μπάλας, αντίστοιχα.

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

Το πρόγραμμά σας θα πρέπει να γράφει στο αρχείο balls.out L γραμμές. Κάθε γραμμή θα έχει έναν ακέραιο που δηλώνει το ελάχιστο πλήθος ελέγχων που πρέπει να γίνουν για κάθε γραμμή της εισόδου.

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

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

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

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

/* Από το μαθητή Μαντουλίδη Χρήστο Απόστολο */
          
#include <cstdio>
using namespace std;
int N, M;


int main() {
  FILE *fIn, *fOut;
  int a, b, m, i;
  int L;
  int ans; 
  
  if ((fIn = fopen("balls.in", "r")) == NULL) return 1;
  fOut = fopen("balls.out", "w");
  fscanf(fIn, "%d", &L);
  while (L--) {
    fscanf(fIn, "%d %d", &N, &M);
    ans = 0;
    a = 1, b = N;
    while (a <= b && a < N) {
      m = (a+b)/2;
      ++ans;
      if (m >= M) {
        for (i = a; i <= M && i < m && i < N; ++i)
          ++ans;
        break;
      } else {
        a = m+1;
      }
    }
    fprintf(fOut, "%d\n", ans);
  }
  fclose(fIn);
  fclose(fOut);
  return 0;
}

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

Πολλές Ελληνικές πόλεις έχουν θέα στη θάλασσα. Οι τιμές των σπιτιών στις πόλεις αυτές είναι ανάλογες της θέας προς τη θάλασσα. Υποθέστε ότι μια πόλη σχηματίζει ένα ορθογώνιο παραλληλόγραμμο με τη δυτική και τη νότια πλευρά να έχουν θέα στα βουνά (όπως το διάγραμμα). Κάθε σπίτι προσδιορίζεται από τις συντεταγμένες x και y. Για να έχει ένα σπίτι hi(xi, yi) καλή θέα δεν πρέπει να υπάρχει άλλο σπίτι hj(xj, yj) ώστε να ισχύει: ??? και ???. Αυτή είναι και η μόνη παράμετρος που επηρεάζει την τιμή των σπιτιών. Δεν υπάρχουν σπίτια που να έχουν την ίδια x συντεταγμένη και το πλήθος των σπιτιών είναι D, που είναι δύναμη του 2.

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

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

Το αρχείο seaview.in στη πρώτη γραμμή περιέχει έναν ακέραιο D (8 ≤ D ≤ 9000000 ) το πλήθος των σπιτιών. Κάθε μια από τις επόμενες D γραμμές περιέχει δύο ακεραίους, που παριστάνουν τις x και y συντεταγμένες των σπιτιών αντίστοιχα, ( 0 ≤ x, y ≤ 14000000).

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

Το αρχείο seaview.out αποτελείται από L γραμμές, όπου το L αντιπροσωπεύει το πλήθος των σπιτιών με τις υψηλότερες τιμές. Κάθε γραμμή θα περιέχει δύο ακέραιους x και y τις συνταγμένες των σπιτιών με την υψηλότερη τιμή. Οι L γραμμές θα πρέπει να εμφανίζονται με αύξουσα σειρά σε σχέση με την x συντεταγμένη.

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

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

Μέγιστος Χρόνος Εκτέλεσης: 13 sec.

Όριο μνήμης: 200 Mbytes.

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

/* Από το μαθητή Καγιά Άρη */
          
#include <stdio.h>
#include <stdlib.h>
long int d;
FILE *fp;
void sinart(void);
long int c[9000000][2], f[9000000][2], fpos = 0, heap;


int main(void)
{
  fp = fopen("seaview.in", "r");
  fscanf(fp, "%ld", &d);
  sinart();
  return 0;
}


void sinart(void)
{
  long int i, j, num;
  short int found = 0;
  for(i=0; i<d; i++) fscanf(fp, "%ld%ld", &c[i][0], &c[i][1]);
  fclose(fp);
  fp = fopen("seaview.out", "w");
  for(i=0; i<d; i++)
  {
    found = 0;
    for(j=0; j<d; j++) 
      if(c[i][0]<c[j][0] && c[i][1]<c[j][1]) {
        found++;
        break;
      }
    if (!found)
    {
      f[fpos][0] = c[i][0];
      f[fpos++][1] = c[i][1];
    }
  }
  for(i=0; i<fpos; i++) 
    for(j=i+1; j<fpos; j++) 
      if(f[i][0]>f[j][0]) {
        num = f[i][0];
        f[i][0] = f[j][0];
        f[j][0] = num;
        num = f[i][1];
        f[i][1] = f[j][1];
        f[j][1] = num;
      }
  for(i=0; i<fpos; i++) fprintf(fp, "%ld %ld\n", f[i][0], f[i][1]);
  fclose(fp);
}