PDP 2013: The last chance

Α: Αναζητώντας Εξωγήινη Νοημοσύνη

Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του 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;  
 }