18ος ΠΔΠ Γ' Φάση
Επιστημονικά Ενδιαφέροντα (diafonies)
[35 Μονάδες]
Στο 10o Πανελλήνιο Συνέδριο Πληροφορικής, κάποιοι επιστήμονες είχαν διαφορετικές (επιστημονικές) απόψεις με κάποιους συναδέλφους τους. Για κάθε επιστήμονα γνωρίζουμε με ποιον από τους άλλους επιστήμονες διαφωνεί. (H σχέση “διαφωνία” είναι συμμετρική: Δηλαδή αν ο 1 διαφωνεί με τον 2, τότε και ο 2 διαφωνεί με τον 1)
Πρόβλημα
Σας ζητούμε να αναπτύξετε πρόγραμμα το οποίο θα ελέγχει αν οι επιστήμονες μπορούν να χωριστούν σε δύο ομάδες εργασίας ώστε να μην υπάρχουν διαφωνίες στην ίδια ομάδα (να μην υπάρχουν δηλαδή επιστήμονες στην ίδια ομάδα που θα διαφωνούν μεταξύ τους). Αν αυτό είναι εφικτό, το πρόγραμμα θα πρέπει να υπολογίζει έναν χωρισμό σε δύο ομάδες εργασίας που δεν περιέχουν διαφωνίες. Διαφορετικά, θα πρέπει να διαπιστώνει ότι αυτό δεν είναι εφικτό.
Αρχεία εισόδου
Το αρχείο diafonies.in στην πρώτη γραμμή έχει έναν ακέραιο αριθμό που δηλώνει τον αριθμό των επιστημόνων \(N\) που συμμετείχαν στο συνέδριο, όπου \(10 \leq N \leq 4.000\). Στις επόμενες \(N\) γραμμές δίδονται: Κατά αύξουσα σειρά οι αριθμοί των επιστημόνων, το πλήθος των άλλων επιστημόνων με τους οποίους διαφωνεί κάθε ένας και οι αριθμοί αυτών με αύξουσα σειρά. (Όλοι οι αριθμοί ξεχωρίζουν με ένα κενό).
Αρχεία εξόδου
Το αρχείο diafonies.out περιέχει δύο (2) γραμμές. Σε κάθε μια από τις δύο υπάρχει ο αριθμός που δηλώνει το πλήθος των επιστημόνων της κάθε ομάδας εργασίας και οι αύξοντες αριθμοί των επιστημόνων που τη συγκροτούν. (Πρώτη είναι η ομάδα με το επιστήμονα με το μικρότερο αύξοντα αριθμό). Όλοι οι αριθμοί χωρίζονται με ένα κενό. Σε περίπτωση που οι επιστήμονες δεν είναι δυνατόν να χωριστούν σε δύο ομάδες το αρχείο περιέχει τους αριθμούς 0 σε δύο γραμμές (κενές ομάδες).
Παραδείγματα αρχείων εισόδου - εξόδου
1o
| diafonies.in | diafonies.out |
|---|---|
| 10 1 2 3 9 2 1 4 3 3 1 4 10 4 2 2 3 5 3 7 8 9 6 1 10 7 2 5 10 8 2 5 10 9 2 1 5 10 4 3 6 7 8 |
4 1 4 5 10 6 2 3 6 7 8 9 |
Περιορισμοί
- Μέγιστος χρόνος εκτέλεσης: 3 δευτερόλεπτα για κάθε τεστ. s