Ζητείται ένα πρόγραμμα που να διαβάζει από το πληκτρολόγιο (standard input) τα παρακάτω:
Στην πρώτη γραμμή, ένα φυσικό αριθμό k.
Στις επόμενες γραμμές μέχρι το τέλος της εισόδου (EOF) ένα σύνολο θετικών φυσικών αριθμών {x1, x2, ..., xn}, καθένας από τους οποίους βρίσκεται σε μία γραμμή.
Το πρόγραμμά σας πρέπει να εκτυπώνει στην οθόνη (standard output) μια γραμμή που να περιέχει:
Τη λέξη true, αν υπάρχει κάποιο υποσύνολο των αριθμών {x1, x2, ..., xn} που να έχει άθροισμα ίσο με k.
Τη λέξη false, αν το παραπάνω δε συμβαίνει.
Το πρόγραμμά σας θα ελεγχθεί αρκετές φορές με διαφορετικά δεδομένα εισόδου, στα οποία το μέγεθος των n, k και των αριθμών {x1, x2, ..., xn} θα διαφέρει σημαντικά. Δώστε έμφαση πρώτα στην εύρεση ενός αποδοτικού αλγόριθμου για την επίλυση του προβλήματος και ύστερα στην αποδοτική υλοποίηση του.
Διευκρινίσεις
Υποβάλλετε όσες λύσεις θέλετε μέσω της αντίστοιχης ιστοσελίδας μέχρι τη Δευτέρα 16/1/2006, ώρα 14:00. Αν υποβάλετε περισσότερες λύσεις, θα ληφθεί υπόψη μόνο η τελευταία.
Οι γλώσσες προγραμματισμού που επιτρέπεται να χρησιμοποιήσετε και ο κανονισμός του διαγωνισμού περιγράφονται στην αρχική σελίδα του διαγωνισμού.
Περισσότερες διευκρινίσεις σχετικά με το πρόβλημα ή με τη διαδικασία του διαγωνισμού δεν πρόκειται να δοθούν. Μην μπείτε στον κόπο να στείλετε e-mail.
Αν πιστεύετε ότι το πρόβλημα ή η διαδικασία του διαγωνισμού περιέχει σφάλματα, ασάφειες, κ.λπ. μπορείτε να μας στείλετε τις παρατηρήσεις σας στη διεύθυνση
, αλλά δεν πρόκειται να σας απαντήσουμε πριν το τέλος του διαγωνισμού.
