Α: Αναζητώντας Εξωγήινη Νοημοσύνη
Πρόβλημα:Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI το οποίο θα διαβάζει τις τιμές που αντιστοιχούν σε ένα σήμα και θα αναγνωρίζει τις χαρακτηριστικές συχνότητες. Μία τριπλέτα σε ένα σήμα είναι μία τριάδα τιμών του σήματος με τις εξής ιδιότητες:
(α) οι δύο ακραίες τιμές ισαπέχουν από τη μεσαία τιμή, και
(β) οι δύο ακραίες τιμές είναι ίσες μεταξύ τους και μικρότερες του μισού της μεσαίας τιμής.
Η μεσαία τιμή μίας τριπλέτας μας δίνει τη χαρακτηριστική συχνότητα, η οποία ισούται με τη θέση της μεσαίας τιμής στο σήμα.
Αρχεία Εισόδου:
Τα αρχεία εισόδου με όνομα seti.in είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς δύο γραμμές. Η πρώτη έχει έναν ακέραιο αριθμό Ν (10 ≤ Ν ≤ 10.000), που αντιστοιχεί στο πλήθος των τιμών του σήματος που έχουμε καταχωρήσει. Η δεύτερη γραμμή έχει Ν ακέραιους αριθμούς χωρισμένους ανά δύο με ένα κενό διάστημα.
Αρχεία Εξόδου:
Τα αρχεία εξόδου με όνομα seti.out είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή έχει έναν ακέραιο αριθμό Κ(0 ≤ Κ ≤ Ν). Ο αριθμός αυτός εκφράζει το πλήθος των χαρακτηριστικών συχνοτήτων που εντοπίστηκαν. Ακολουθούν Κ γραμμές, κάθε μια από τις οποίες έχει έναν ακέραιο αριθμό Μ, (2 ≤ Μ ≤ Ν-1). Ο αριθμός Μ εκφράζει μία χαρακτηριστική συχνότητα, δηλαδή τη θέση της μεσαίας τιμής της αντίστοιχης τριπλέτας μέσα στο σήμα (η αρίθμηση αρχίζει από το 1). Οι χαρακτηριστικές συχνότητες πρέπει να δίνονται σε αύξουσα σειρά. Αν σε μία χαρακτηριστική συχνότητα αντιστοιχούν περισσότερες τριπλέτες, η συχνότητα θα πρέπει να εμφανίζεται μόνο μία φορά.
#include <stdio.h>
#define MAX 10000
#define DEBUG0
int N;
int Amp[MAX]; //input
bool isTriplet[MAX]; //result
int nTriplets;
int main() {
#ifndef DEBUG
freopen("seti.in", "rt", stdin);
freopen("seti.out", "wt", stdout);
#endif
//input
scanf("%d", &N);
for (int i=0; i<N; i++) {
scanf("%d", &Amp[i]);
}
//find triplets
for (int i=0; i<N; i++) {
for (int j=1; i-j>=0 && i+j<N; j++) {
if (Amp[i-j] == Amp[i+j] && Amp[i-j] < Amp[i]/2.) {
//found triplet!
isTriplet[i] = true;
nTriplets++;
break;
}
}
}
//output
printf("%d\n", nTriplets);
for (int i=0; i<N; i++) {
if (isTriplet[i]) printf("%d\n",i+1);
}
return 0;
}
Β: Οι μυστικοί αριθμοί
Πρόβλημα:Στο δείπνο που παρατίθεται κατά τη διάρκεια του φετινού πανελλήνιου συνεδρίου πληροφορικής παρευρίσκονται Ν επιστήμονες. Κάθε ένας έχει στο μυαλό του ένα θετικό φυσικό αριθμό, διαφορετικό από τους αριθμούς όλων των συναδέλφων του, τον οποίο κρατάει μυστικό. Ο διοργανωτής του δείπνου θέλει να μοιράσει τους επιστήμονες σε ομάδες, αποτελούμενες από ένα ή περισσότερα μέλη, ούτως ώστε σε καμία ομάδα να μην υπάρχουν δύο επιστήμονες που ο μυστικός αριθμός του ενός να διαιρεί ακριβώς το μυστικό αριθμό του άλλου. Είναι αδύνατο να μάθετε τους μυστικούς αριθμούς των επιστημόνων. Με πολύ κόπο, καταφέρνετε να βρείτε μερικές δυάδες επιστημόνων που είναι φίλοι και για τους οποίους γνωρίζετε με βεβαιότητα ότι ο μυστικός αριθμός του πρώτου διαιρεί ακριβώς το μυστικό αριθμό του δεύτερου. Μπορείτε να υπολογίσετε τον ελάχιστο αριθμό ομάδων που θα χρειαστεί να φτιάξει ο διοργανωτής του δείπνου;
Αρχεία εισόδου:
Τα αρχεία εισόδου με όνομα scidinner.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή περιέχουν δύο φυσικούς αριθμούς Ν και Μ χωρισμένους με ένα κενό διάστημα (1 ≤ M ≤ Ν ≤ 1.000.000), όπου Ν το πλήθος των επιστημόνων και M το πλήθος των δυάδων των φίλων. Θεωρούμε ότι οι επιστήμονες είναι αριθμημένοι από 1 έως και Ν. Κάθε μία από τις επόμενες Μ γραμμές περιέχει δύο φυσικούς αριθμούς xi και yi χωρισμένους με ένα κενό διάστημα (1 ≤ xi , yi ≤ Ν), που ορίζουν μία δυάδα φίλων: γνωρίζουμε ότι ο μυστικός αριθμός του επιστήμονα xi διαιρεί ακριβώς το μυστικό αριθμό του επιστήμονα yi. Δε θα υπάρχουν δύο δυάδες με το ίδιο yi.
Αρχεία εξόδου:
Τα αρχεία εξόδου με όνομα scidinner.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει έναν ακέραιο αριθμό Κ (1 ≤ Κ ≤ Ν). Ο αριθμός αυτός εκφράζει το ελάχιστο πλήθος ομάδων επιστημόνων που πρέπει να φτιάξει ο διοργανωτής του δείπνου.
#undef DEBUG
#define DEBUG0
#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) do ; while(0)
#define NDEBUG
#endif
#include <assert.h>
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 1000001
int N,M;
vector<int> graph[MAX];
int memo[MAX]; // memorization
int fmax(int n); //recursive function
int main() {
#ifndef DEBUG
freopen("scidinner.in", "rt", stdin);
freopen("scidinner.out", "wt", stdout);
#endif
scanf("%d %d", &N, &M);
for (int i=1; i<=N; i++) { memo[i] = 1; }//no children by default
//read nodes
int from, to;
for (int i=0; i<M; i++) {
scanf("%d %d", &from, &to);
graph[from].push_back(to);
memo[from] = 0; //has children to check
assert(from!=to &&
from>0 && from <=N &&
to >0 && to <=N );
}
int totalmax = 1; //totalmax = minteams ;)
for (int i = 1; i <= N; i++) {
memo[i] = fmax(i);
totalmax = max(totalmax, memo[i]);
}
printf("%d", totalmax);
return 0;
}
int fmax(int u) {
if (memo[u] != 0) return memo[u];
int res = 1;
for (int j=0; j<graph[u].size(); j++) {
int v = graph[u][j];
res = max(res, fmax(v)+1);
}
assert(res>1);
return res;
}
.png)
.png)
.png)
ε1, ε2, ε3 αντίστοιχα.
