Αρχική > 22ος ΠΔΠ

22ος ΠΔΠ Γ' Φάση
Servers (servers)

[35 Μονάδες]

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

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

Πρόβλημα

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

Παράδειγμα: Για \(N=5\) servers και \(M=5\) σελίδες

\(S_1\) \(S_2\) \(S_3\) \(S_4\) \(S_5\)
\(3 \mapsto 99\) \(1 \mapsto 91\) \(1 \mapsto 92\) \(3 \mapsto 74\) \(3 \mapsto 67\)
\(1 \mapsto 66\) \(3 \mapsto 90\) \(3 \mapsto 75\) \(1 \mapsto 56\) \(4 \mapsto 67\)
\(0 \mapsto 63\) \(0 \mapsto 61\) \(4 \mapsto 70\) \(2 \mapsto 56\) \(1 \mapsto 58\)
\(2 \mapsto 48\) \(4 \mapsto 07\) \(2 \mapsto 16\) \(0 \mapsto 28\) \(2 \mapsto 54\)
\(4 \mapsto 44\) \(2 \mapsto 01\) \(0 \mapsto 01\) \(4 \mapsto 19\) \(0 \mapsto 35\)

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

Top 5
\(3 \mapsto 405\)
\(1 \mapsto 363\)
\(4 \mapsto 207\)
\(0 \mapsto 188\)
\(2 \mapsto 175\)

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

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα servers.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν τρεις αριθμούς \(M\), \(N\), \(K\). Τον αριθμό \(M\) των φιλοξενούμενων σελίδων (\(5 \leq M \leq 10.000\)).

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

Aρχεία εξόδου

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

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

servers.in servers.out
5 5 2
3 99 1 91 1 92 3 74 3 67
1 66 3 90 3 75 1 56 4 67
0 63 0 61 4 70 2 56 1 58
2 48 4 07 2 16 0 28 2 51
4 44 2 01 0 01 4 19 0 35
3 405
1 363

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