28ος ΠΔΠ Α' Φάση
Υπερυπολογιστής ARIS (aris)

Το Υπουργείο Παιδείας ανακοίνωσε ότι, από φέτος, ο εγκατεστημένος σε ειδικό χώρο του υπουργείου, υπερυπολογιστής ARIS τίθεται στη διάθεση της επιστημονικής και ερευνητικής κοινότητας. Κατά τη διάρκεια ενός 24ωρου η υπολογιστική ισχύς του θα διατίθεται σε \(M\) το πολύ ερευνητικές ομάδες αριθμημένες από \(1\) έως \(M\)), κάθε μία από τις οποίες θα τον χρησιμοποιεί για να εκτελέσει ένα πρόγραμμα επεξεργασίας δεδομένων.

Προκειμένου να μοιράζεται δίκαια η υπολογιστική ισχύς κατά τη διάρκεια του 24ώρου, το πρόγραμμα κάθε ομάδας μπορεί να εκτελείται συνεχόμενα μόνο για ένα μικρό χρονικό διάστημα, που το ονομάζουμε “παράθυρο εκτέλεσης”. Στη συνέχεια, η εκτέλεση του προγράμματος διακόπτεται, αν φυσικά δεν έχει ολοκληρωθεί, για να συνεχιστεί σε μεταγενέστερο χρόνο αφού πρώτα εκτελεστούν τα προγράμματα άλλων ομάδων. Κάθε 24ωρο χωρίζεται σε \(N\) ίσης διάρκειας παράθυρα εκτέλεσης και η σειρά με την οποία εκτελούνται τα προγράμματα των ομάδων καταγράφεται σε ένα ημερήσιο αρχείο.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις Γλώσσες του IOI (Pascal, C, C++, Java) το οποίο, αφού διαβάσει το αρχείο καταγραφής της εκτέλεσης των προγραμμάτων θα υπολογίζει:

Πόσα προγράμματα εκτελέστηκαν
Πόσα παράθυρα εκτέλεσης δόθηκαν στο πρόγραμμα που απαιτούσε τη λιγότερη υπολογιστική ισχύ, και
Πόσα παράθυρα εκτέλεσης δόθηκαν στο πρόγραμμα που απαιτούσε την περισσότερη υπολογιστική ισχύ

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

Τα αρχεία εισόδου με όνομα aris.in είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς δύο γραμμές.

Η πρώτη γραμμή περιέχει δύο ακέραιους \(N\) (το πλήθος των παραθύρων εκτέλεσης) και \(M\) (το πλήθος των ερευνητικών ομάδων) που χωρίζονται μεταξύ τους με ένα κενό διάστημα.
Η δεύτερη γραμμή περιέχει ακριβώς \(N\) ακέραιους \(S_i\) (\(1 \le S_i \le M\), όπου \(1 \le i \le N\)) που χωρίζονται μεταξύ τους με ένα κενό διάστημα. Ο ακέραιος \(S_i\) είναι ο αριθμός της ομάδας το πρόγραμμα της οποίας εκτελέστηκε στο \(i\)-οστό παράθυρο εκτέλεσης.

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

Τα αρχεία εξόδου με όνομα aris.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει τρεις ακέραιους αριθμούς \(K\), \(X\), \(Y\), χωρισμένους μεταξύ τους με ένα κενό διάστημα.

\(K\): το πλήθος των ομάδων, τα προγράμματα των οποίων εκτελέστηκαν κατά τη διάρκεια του 24ώρου (\(Κ \le Μ\)). Προσέξτε ότι μπορεί να είναι \(K < M\), αν τα προγράμματα κάποιων ομάδων δεν εκτελεστούν καθόλου κατά τη διάρκεια του 24ώρου.
\(X\): το συνολικό πλήθος των παραθύρων εκτέλεσης για το πρόγραμμα που εκτελέστηκε τις λιγότερες φορές (\(X \le N\)).
\(Y\): το συνολικό πλήθος των παραθύρων εκτέλεσης για το πρόγραμμα που εκτελέστηκε τις περισσότερες φορές (\(Y \le N\)).

Όρια

\(1 \le N, M \le 1.000.000\),
\(1 \le S_i \le M\).

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

aris.in	aris.out
10 5 1 2 3 4 1 5 1 5 2 1	5 1 4

Εξήγηση: Εκτελέστηκαν συνολικά τα προγράμματα 5 ομάδων (με αριθμούς 1, 2, 3, 4, 5). Στα προγράμματα των ομάδων 3 και 4 δόθηκε ο λιγότερος συνολικός χρόνος (1 παράθυρο εκτέλεσης), ενώ στο πρόγραμμα της ομάδας 1 δόθηκε ο περισσότερος (4 παράθυρα εκτέλεσης).

aris.in	aris.out
12 6 3 5 5 1 2 3 1 5 3 5 3 2	4 2 4