36ος ΠΔΠ Γ' Φάση
Γραφειοκρατεία (bureaucracy)

Ο γραφειοκρατικός μηχανισμός της χώρας ασχολείται με την επεξεργασία εγγράφων. Για την επεξεργασία ενός εγγράφου πρέπει κάποιος υπάλληλος να εργασθεί κάποιες ώρες, ο αριθμός των οποίων είναι εκ των προτέρων γνωστός. Ως αποτέλεσμα, δημιουργείται ένα άλλο έγγραφο.

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

Κάθε υπάλληλος δουλεύει το πολύ \(L\) ώρες την ημέρα και για τη δουλειά αυτή πληρώνεται με ένα χρυσό νόμισμα. Κατά τη διάρκεια της ημέρας, επεξεργάζεται ακριβώς ένα έγγραφο, υπό την προϋπόθεση ο χρόνος επεξεργασίας να μην υπερβαίνει τις \(L\) ώρες. Αυτό σημαίνει ότι καμία επεξεργασία εγγράφου που απαιτεί πάνω από \(L\) ώρες δεν είναι δυνατό να γίνει. Έτσι εξηγείται γιατί κάποια πράγματα “χάνονται στη γραφειοκρατία!”

Ο προϊστάμενος επιλέγει \(D\) υπαλλήλους και αναθέτει σε καθέναν από αυτούς να δημιουργήσει ένα από τα \(D\) τελικά έγγραφα (συγκεκριμένο και διαφορετικό). Κάθε υπάλληλος ξεκινά από ένα αρχικό έγγραφο της επιλογής του. (Θεωρήστε ότι υπάρχει ανεξάντλητο απόθεμα αρχικών εγγράφων και ότι μπορούν περισσότεροι υπάλληλοι να ξεκινήσουν από το ίδιο αρχικό έγγραφο.) Αν ο υπάλληλος είναι τυχερός, αυτό είναι το ίδιο με το τελικό έγγραφο που του έχει ανατεθεί και δε χρειάζεται να κάνει τίποτα, άρα δε χρειάζεται να δουλέψει καμία μέρα και δε θα πληρωθεί κανένα χρυσό νόμισμα. Διαφορετικά, ο υπάλληλος θα χρειαστεί μία ή περισσότερες μέρες για να δημιουργήσει το τελικό έγγραφο που του έχει ανατεθεί, κάνοντας μία κατάλληλη επεξεργασία την ημέρα. Τα ενδιάμεσα έγγραφα που τυχόν θα δημιουργήσει στην πορεία τα πετάει στα σκουπίδια, ανεξαρτήτως αν είναι τελικά και έχουν ανατεθεί σε άλλους συναδέλφους του, στους οποίους θα μπορούσαν να είναι χρήσιμα!

Οι υπάλληλοι φυσικά θέλουν να δουλεύουν όσο γίνεται λιγότερες ώρες την ημέρα. Αν λοιπόν καθένας από αυτούς κάνει τις καλύτερες δυνατές επιλογές εγγράφων προς επεξεργασία, βρείτε την ελάχιστη δυνατή τιμή του \(L\) που επαρκεί για να μπορούν να δημιουργηθούν όλα τα τελικά έγγραφα. Επίσης, για την ελάχιστη τιμή του \(L\), βρείτε το πλήθος \(C\) των χρυσών νομισμάτων που θα πρέπει να πληρωθούν συνολικά οι υπάλληλοι (δηλαδή το συνολικό πλήθος ημερών που θα δουλέψουν).

Θεωρήστε δεδομένο ότι όλα τα τελικά έγγραφα θα είναι δυνατό να δημιουργηθούν με τη διαδικασία που περιγράφηκε, αρκεί η τιμή του \(L\) να είναι αρκετά μεγάλη.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες PASCAL, C, C++, Java, το οποίο θα διαβάζει τα δεδομένα των εγγράφων και θα εκτυπώνει τις ζητούμενες τιμές των \(L\) και \(C\).

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

Το αρχείο εισόδου με όνομα bureaucracy.in είναι αρχείο κειμένου με την εξής δομή. Η πρώτη γραμμή της περιέχει τέσσερις ακέραιους αριθμούς \(N\), \(S\), \(D\) και \(R\), χωρισμένους ανά δύο με ένα κενό διάστημα. Το \(N\) είναι το συνολικό πλήθος των εγγράφων, το \(S\) είναι το πλήθος των αρχικών εγγράφων, το \(D\) είναι το πλήθος των τελικών εγγράφων, και το \(R\) είναι το πλήθος των διαφορετικών δυνατών επεξεργασιών εγγράφων. Η δεύτερη γραμμή της εισόδου θα περιέχει \(S\) ακέραιους αριθμούς, χωρισμένους ανά δύο με ένα κενό διάστημα: τους αριθμούς των αρχικών εγγράφων. Ομοίως, η τρίτη γραμμή θα περιέχει \(D\) ακέραιους αριθμούς: τους αριθμούς των τελικών εγγράφων. Κάθε μία από τις επόμενες \(R\) γραμμές θα περιέχει τρεις ακέραιους αριθμούς \(A\), \(B\) και \(E\), χωρισμένους ανά δύο με ένα κενό διάστημα, που περιγράφουν μία δυνατή επεξεργασία: από το έγγραφο \(A\) προκύπτει το έγγραφο \(B\) και η επεξεργασία αυτή απαιτεί \(E\) ώρες.

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

Το αρχείο εξόδου με όνομα bureaucracy.out είναι αρχείο κειμένου με μία μόνο γραμμή, που πρέπει να περιέχει δύο ακέραιους αριθμούς, \(L\) και \(C\), χωρισμένους με ένα κενό διάστημα. To \(L\) πρέπει να είναι η ελάχιστη τιμή των ωρών εργασίας ανά ημέρα ώστε να μπορούν να δημιουργηθούν όλα τα τελικά έγγραφα, και το \(C\) το ελάχιστο πλήθος νομισμάτων που θα δαπανηθούν για αυτή την τιμή του \(L\).

Παράδειγμα αρχείου εισόδου και εξόδου:

bureaucracy.in	bureaucracy.out
7 2 4 9 1 3 4 7 3 6 1 2 2 3 7 3 2 4 3 4 5 1 4 2 2 5 7 2 3 6 4 5 6 1 1 7 5	3 7

Εξήγηση: Υπάρχουν 7 είδη εγγράφων, αριθμημένα από 1 μέχρι και 7. Αρχικά είναι τα έγγραφα 1 και 3. Τελικά είναι τα έγγραφα 4, 7, 3 και 6. Προσέξτε ότι το έγγραφο 3 είναι συγχρόνως και αρχικό και τελικό, επομένως ο υπάλληλος στον οποίο θα ανατεθεί δεν χρειάζεται να κάνει τίποτα.

Επιλέγοντας \(L = 3\) ώρες εργασίας ανά ημέρα, ο υπάλληλος που πρέπει να δημιουργήσει το τελικό έγγραφο 4 μπορεί να ξεκινήσει από το 1 και να ακολουθήσει την πορεία 1 → 2 → 4, δουλεύοντας συνολικά 2 μέρες. Ο υπάλληλος που πρέπει να δημιουργήσει το τελικό έγγραφο 6 μπορεί κι αυτός να ξεκινήσει από το 1 και να ακολουθήσει την πορεία 1 → 2 → 4 → 5 → 6, δουλεύοντας συνολικά 4 μέρες. Τέλος, ο υπάλληλος που πρέπει να δημιουργήσει το τελικό έγγραφο 7 μπορεί να ξεκινήσει από το 3 και να ακολουθήσει την πορεία 3 → 7, δουλεύοντας συνολικά μόνο 1 μέρα. Έτσι, η δημιουργία όλων των τελικών εγγράφων θα κοστίσει συνολικά \(C = 2 + 4 + 1 = 7\) χρυσά νομίσματα.

Με μικρότερη τιμή του \(L\), π.χ. \(L = 2\), μόνο το τελικό έγγραφο 3 είναι δυνατόν να παραχθεί.

Περιορισμοί:

• \(2 \le N \le 10.000\).
• \(1 \le S \le N\) και \(1 \le D \le N\).
• \(1 \le R \le 100.000\).
• \(1 \le A \le N\) και \(1 \le B \le N\) και \(A \neq B\).
• \(1 \le E \le 1.000.000.000\).

Subtasks:

• Για περιπτώσεις ελέγχου συνολικής αξίας \(20\%\), θα είναι \(2 \le N \le 10\).
• Για περιπτώσεις ελέγχου συνολικής αξίας \(40\%\), θα είναι \(2 \le N \le 1.000\). και \(1 \le E \le 1.000\).
• Για περιπτώσεις ελέγχου συνολικής αξίας \(60\%\), θα είναι \(2 \le N \le 1.000\).

Προσοχή! Φροντίστε να διαβάζετε την είσοδο και να εκτυπώνετε την έξοδο αποδοτικά, ειδικά αν προγραμματίζετε σε C++ ή Java.

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