Δημοσιεύτηκε: 02 Απρ 2012, 16:50
stamatiou έγραψε:Καταρχάς, βλέπω ότι αν αθροίσουμε το -101 με όλα τα υπόλοιπα θα βγεί ένας πίνακας αθροισμάτων:
(εδώ γράφω την απόλυτη τιμή του αθροίσματος)Spoiler: show
Παρατηρώ ότι ενώ στην αρχή η διάταξη είναι φθίνουσα ενώ στο 6 και αλλάζει σε αύξουσα. Όταν κάνω έναν παρόμοιο πινακα αλλά με το -4 βγαίνει:Spoiler: show
Εδώ συμβαίνει το ίδιο. αν κάνω και άλλο πίνακα για το -1 θα γίνει πάλι αυτή η αλλαγή από φθίνουσα σε αύξουσα. Επίσης παρατηρώ ότι ο αριθμός που γίνεται η αλλαγή είναι πάντα πριν από τον αριθμό που είχε γίνει η προηγούμενη άρα δεν χρειάζεται να ελέγχω παραπέρα. Και για να το εκμεταλλευτώ αυτό, δεν διαβάζω όλο το αρχείο εισόδου αλλά μόνο μέχρι να γίνει η αλλαγή διάταξης.
Από την εκφώνηση αναφέρει ότι το N < 1.000.000, και ότι μπορείς να χρησιμοποιήσεις μέχρι 64MB RAM. Με 1 εκατομμύριο long int (8byte), δεσμεύεις 8ΜΒ RAM που είναι μέσα στα όρια αν διάβαζες όλο το αρχείο στη μνήμη.
Σαν εξάσκηση θα πρότεινα να επιλύσεις μια φορά την εργασία με αυτό το τρόπο, με χρήση πίνακα.
Για την ανάγνωση όλου του αρχείου των 1000000 αριθμών σε ένα πίνακα, παίρνει γύρω στα 170ms στον υπολογιστή μου (φτιάχνεις το εκτελέσιμο, και τρέχεις time ./myprog). Το μέγιστο στην εκτέλεση είναι 3000ms (3 δευτερόλεπτα) που είναι μέσα στα όριά σου.
Με τη χρήση του πίνακα, βρίσκεις που είναι το 0 (ή το νούμερο που είναι πιο κοντά στο μηδέν).
Και μετά, δοκιμάζεις ζευγάρια από νούμερα (μεγαλύτερα+μικρότερα του πιο κοντινού αριθμού στο 0) για να βρεις τα καλύτερα ζευγάρια.
Κάτι άλλο που προτείνω στον κώδικά σου είναι να προσθέτεις εντολές printf() συχνά ώστε να παρακολουθείς εύκολα τι παίρνει χρόνο κατά την εκτέλεση.