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

18ος ΠΔΠ Γ' Φάση
Πρακτική Άσκηση (practice)

[40 Μονάδες]

Η Ελληνική Εταιρεία Επιστημόνων & Επαγγελματιών Πληροφορικής και Επικοινωνιών (ΕΠΥ) ανέλαβε από το Ακαδημαϊκό Έτος 2006-07 το συντονισμό της πρακτικής άσκησης των φοιτητών των τμημάτων Μηχανικών Η/Υ, Πληροφορικής και Τηλεπικοινωνιών των Ελληνικών Πανεπιστημίων. Στο πρόγραμμα πρακτικής άσκησης δήλωσαν συμμετοχή \(N\) φοιτητές των αντιστοίχων τμημάτων (\(4 \leq N \leq 1.000\)). Οι προσφερόμενες θέσεις πρακτικής άσκησης είναι \(M\) (\(N \leq M \leq 1.500\)). Ο Πίνακας \(P[I, J]\) έχει τιμή \(1\) αν ο φοιτητής \(I\) ενδιαφέρεται για τη θέση \(J\) και \(0\) στην αντίθετη περίπτωση.

Πρόβλημα

Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα εξασφαλίζει πρακτική άσκηση σε όσο μεγαλύτερο αριθμό φοιτητών γίνεται.

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

Το αρχείο practice.in στην πρώτη γραμμή έχει δύο αριθμούς: τον αριθμό \(N\) των ενδιαφερομένων φοιτητών και τον αριθμό \(M\) των προσφερομένων θέσεων που χωρίζονται με ένα κενό. Κάθε μία από τις επόμενες \(N\) σειρές περιέχει \(M\) ψηφία \(0\) ή \(1\), τα οποία χωρίζονται μεταξύ τους με ένα κενό και αναπαριστούν τις δηλώσεις των φοιτητών για τις αντίστοιχες θέσεις.

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

Το αρχείο practice.out περιέχει μία γραμμή με \(N\) αριθμούς, όπου κάθε αριθμός βρίσκεται στο διάστημα \([0..M]\). Ο πρώτος αριθμός δηλώνει τη θέση που θα καταλάβει ο πρώτος φοιτητής, ο δεύτερος αριθμός τη θέση που θα καταλάβει ο δεύτερος φοιτητής κοκ. (Φοιτητής με αριθμό 0 σημαίνει ότι δεν βρήκε θέση πρακτικής άσκησης της επιλογής του).

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

1o

practice.in practice.out
4 5
1 0 1 1 0
1 0 0 0 0
0 1 1 0 0
0 0 0 1 0
3 1 2 4

Περιορισμοί

  • Μέγιστος χρόνος εκτέλεσης: 5 δευτερόλεπτα για κάθε τεστ.