Β' Φάση ΠΔΠ

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από compileGuy »

chris έγραψε:Μάλλον... Εγώ βρίσκω τις αποστάσεις ΟΛΩΝ των δυνατών ζευγαριών!
δηλαδή 1-5,1-4,1-3,1-2,2-5,2-4,2-3,3-5,3-4,4-5! Που σημαίνει ότι στα 1000 αεροπλάνα βρίσκω την απόσταση 500501 ζευγαριών, και μετά το ελάχιστο αυτών! :!:

Και ξαρωτάω: Στα παραδείγματα οι αριθμοί της εξόδου είναι διαδοχικοί! Αρκεί να βρούμε τις αποστάσεις των 1-2,2-3,3-4,4-5; :?:

Μάλλον κάτι έχω καταλάβει λάθος. :?
Φίλε υπάρχει πιό εύκολος τρόπος!! Για σκέψου λίγο.. Δεν χρειάζεται να βρείς την κάθε απόσταση! ;)

ΥΓ:Δεν νομίζω να επιτρέπεται να βοηθήσω και άλλο :?
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Spoiler: show
Δε ξέρω αν υπάρχει κάποιος (μαντικός μάλλον) τρόπος στον οποίο δεν βρίσκεις κάθε απόσταση αλλά η λογική του chris (αν και ανάποδη στη σειρά) μάλλον είναι σωστή.
Οι αριθμοί στην έξοδο τυχαίνει να ειναι διαδοχικοί. Δεν υπάρχει καμία εγγύηση για αυτό.

Όσον αφορά το χρόνο (αφού με αυτά που άκουσα αποφάσισα να το λύσω να δω τι γίνεται) κάνει περίπου 0.1sec για 1000.
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από georgeha98 »

chris έγραψε:Επιτέλους!

Εγώ πάω γυμνάσιο, και από όσο είδα, δεν μου φάνηκε και έυκολο το θέμα...
:o :shock: :? :roll:
Θα μας δίνονται συντεταγμένες των αεροπλάνων σε έναν τρισδιάστατο πίνακα και εμείς θα πρέπει να βρούμε ποιά αεροπλάνα είναι πιο κοντά. Έτσι;

Δεν έχω ιδέα πως θα το κάνω κάτι τέτοιο. Αλλά που θα πάει κάτι θα βρώ!!!

Και τι είναι "άπλειστος" αλγόριθμος; Δεν έβγαλα άκρη ψάχνοντας στο google...
:?:


edit: Άλλο άπλειστος και άλλο άπληστος εεε;
Ψάξε για Greedy Algorithm, δεν είναι τόσο τρομερό, κάπου θα βρεις κάτι.
http://en.wikipedia.org/wiki/Greedy_algorithm
Εδώ έχει πληροφορίες, αλλά ελπίζω να μην ψάχνεις για κανά αλγόριθμο, που θα σου λύσει το πρόβλημα, σκέψου, αν θυμάμαι καλά έχει κάτι μέσα στο forum που μπορεί να σε βοηθήσει
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από compileGuy »

thelastnicholas έγραψε:
Spoiler: show
Δε ξέρω αν υπάρχει κάποιος (μαντικός μάλλον) τρόπος στον οποίο δεν βρίσκεις κάθε απόσταση αλλά η λογική του chris (αν και ανάποδη στη σειρά) μάλλον είναι σωστή.
Οι αριθμοί στην έξοδο τυχαίνει να ειναι διαδοχικοί. Δεν υπάρχει καμία εγγύηση για αυτό.

Όσον αφορά το χρόνο (αφού με αυτά που άκουσα αποφάσισα να το λύσω να δω τι γίνεται) κάνει περίπου 0.1sec για 1000.
Κοίτα εγώ βρίσκω πχ 1-2, 1-3, 1-4.... αλλα μετά 5-6, 5-7.. και όχι τα 5-1 , 5-2 κτλ.

Ίσως υτό να είναι το πρόβλημα του chris!

@thelastnicolas
Εμένα κάνει 300ms περίπου!!
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Σε μια πολύ πρόχειρη υλοποίηση είναι σε εμένα 0m0.169s

Δεν έχει σημασία η σειρά με την οποία τα εξετάζεις.

Με το κλασικός άπληστος αλγόριθμος μάλλον αναφέρονταν στην λογική παρά σε κάποιο συγκεκριμένο αλγόριθμο.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από userresu »

Μήπως το παρακάναμε λίγο με τα spoilers;
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thetrojan01 »

Κώδικας: Επιλογή όλων

[thetrojan01@thetrojan01-labs airforce]$ time ./airforce

real	0m0.106s
user	0m0.030s
sys	0m0.003s
στη χειρότερη περίπτωση. Όσο λιγότερο είναι το Ν τόση λιγότερη μνήμη πιάνει το πρόγραμμά μου (προγραμματιστές σε C++, καταλαβαίνετε, έτσι;)


Οκ το 'χω λύσει...
Ίσως το ξαναυλοποιήσω καλύτερο, δεν ξέρω...
Τέλως πάντων, θα τα πούμε μετά το πέρας των υποβολών! :D
Spoiler: show
Μειώνετε τη ζωή του ποντικιού σας κλικάροντας στα σπόιλερ! :lol:
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από userresu »

thetrojan01 έγραψε:στη χειρότερη περίπτωση. Όσο λιγότερο είναι το Ν τόση λιγότερη μνήμη πιάνει το πρόγραμμά μου (προγραμματιστές σε C++, καταλαβαίνετε, έτσι;)
Δεν νομίζω να έχει νόημα αυτό, επειδή δεν βαθμολογείσαι στο πόση μνήμη πιάνει το πρόγραμμα. ;)
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thetrojan01 »

userresu έγραψε:
thetrojan01 έγραψε:στη χειρότερη περίπτωση. Όσο λιγότερο είναι το Ν τόση λιγότερη μνήμη πιάνει το πρόγραμμά μου (προγραμματιστές σε C++, καταλαβαίνετε, έτσι;)
Δεν νομίζω να έχει νόημα αυτό, επειδή δεν βαθμολογείσαι στο πόση μνήμη πιάνει το πρόγραμμα. ;)
Σε περίπτωση ισοψηφίας, τότε ναι.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Δε νομίζω οτι βαθμολογείται η κατανάλωση μνήμης. Μονο σε πολύ ακραιες περιπτωσεις μπορεί να συμβεί αυτό. Μέχρι στιγμής δεν νομίζω οτι εχει συμβεί ποτε.
nick@debian:~/Desktop$ g++ gymnasium.cpp
nick@debian:~/Desktop$ time ./a.out
real 0m0.016s
user 0m0.012s
sys 0m0.004s

(*Λάθος πρόγραμμα-Διορθώθηκε--updated)
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από georgeha98 »

Μήπως έλυσε κανείς του Λυκείου? Έχει δοκιμάσει χρόνο σε μεγάλο testcase?
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Αυτό ειναι μεγάλο θέμα.... Ενταξει οι δυο πρωτοι τρόποι είναι ευκολοι...
(Αλλα αργοι....)
Τώρα οσον αφορά τη ν^α ,α Ε Ζ, 1<α<4 δε ξέρω.... ;-)
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Β' Φάση ΠΔΠ

Δημοσίευση από kernelpanic »

thelastnicholas έγραψε:Δε νομίζω οτι βαθμολογείται η κατανάλωση μνήμης. Μονο σε πολύ ακραιες περιπτωσεις μπορεί να συμβεί αυτό. Μέχρι στιγμής δεν νομίζω οτι εχει συμβεί ποτε.
Ο μόνος πιθανός τρόπος σ'αυτό το πρόβλημα να μείνεις από μνήμη είναι να φτιάξεις έναν βρόχο που θα δεσμεύει συνέχεια μνήμη, οπότε...
...
...
:twisted:*evil γελάκι*
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thetrojan01 »

Κώδικας: Επιλογή όλων

[thetrojan01@thetrojan01-labs airforce]$ time ./airforce

real	0m0.034s
user	0m0.030s
sys	0m0.003s
Το θέμα γυμνασίου χωρίς δυναμική μνήμη αυτή τη φορά ;)
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
bour1992
Δημοσιεύσεις: 55
Εγγραφή: Πέμ Δεκ 18, 2008 1:50 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από bour1992 »

Όταν η διευκρίνιση 1 λέει πως "Οι στογγυλοποιήσεις των αποστάσεων γίνονται μόνο μια φορά στο τέλος, Ενδιάμεσα οι αριθμοί έχουν δεκαδικό όρισμα" ενοεί πως οι ενδιάμεσες αποστάσεις είναι δεκαδικοί αριθμοί με πόσα δεκαδικά ψηφία?
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Έχει σημασια?
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από thelastnicholas »

Θέλω να πω δεν πειράζεις τίποτα ενδιάμεσα είτε προς τα πάνω είτε προς τα κάτω( οι μεταβλητές κινητής υποδιαστολής επαρκούν). Στρογυλοποίηση κάνεις μόνο στο τελικό αποτέλεμσα
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από compileGuy »

Ερώτηση: Πιστεύεται πως θα δω διαφορά χρόνου (απο 300ms) απο windows που το τρέχω σε linux??
Και αν ναι θα είναι αξιόλογη???
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Β' Φάση ΠΔΠ

Δημοσίευση από kernelpanic »

Ναι, το linux είναι πολύ ελαφρύτερο, αλλά δεν έχει σημασία.
Ο κώδικας θα compilαριστεί με βιβλιοθήκες συμβατές με (σχεδόν) όλα τα λειτουργικά.
Θα τους στείλεις τον κώδικα, ο οποίος θα εκτελεστεί θε ένα μηχάνημα τρελής υπολογιστικής ισχύος.
Όσο και να τρέχει, πρόσεξε τη διαφορά μεταξύ των εκδόσεων. Αυτή έχει σημασία.
Ο χρόνος εκτέλεσης στο δικό σου μηχάνημα δε σημαίνει τίποτα στον Τάλω, ο 600άρης μου σούρνεται και πάλι ο κώδικας δεν έχει κανένα απολύτως πρόβλημα.
Δοκίμασε με 1000 αεροπλανάκια, και αν είναι <5" μάλλον δε θα΄χεις προβλήματα χρόνου. ;)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Β' Φάση ΠΔΠ

Δημοσίευση από compileGuy »

Θέλω πολύ να περάσω στην άλλη φάση και υπολογίζω το κάθε ms!! :D :D

Πάντος στον Talos μου έδειχνε 0.000 σε όλα τα testcase και με 1000 αεροπλάνα κανει 300ms!! :) Ελπίζω να περάσω!!
Απάντηση