Β' Φάση ΠΔΠ

[userresu]

Ανακοινώθηκαν τα θέματα της Β φάσης, που φέτος είναι ξεχωριστά σε Γυμνάσιο-Λύκειο (!)
Καιρός ήταν να γίνει αυτό

[chris]

Επιτέλους!

Εγώ πάω γυμνάσιο, και από όσο είδα, δεν μου φάνηκε και έυκολο το θέμα...

Θα μας δίνονται συντεταγμένες των αεροπλάνων σε έναν τρισδιάστατο πίνακα και εμείς θα πρέπει να βρούμε ποιά αεροπλάνα είναι πιο κοντά. Έτσι;

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

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



edit: Άλλο άπλειστος και άλλο άπληστος εεε;

[compileGuy]

Επιτέλους!

Εγώ πάω γυμνάσιο, και από όσο είδα, δεν μου φάνηκε και έυκολο το θέμα...

Θα μας δίνονται συντεταγμένες των αεροπλάνων σε έναν τρισδιάστατο πίνακα και εμείς θα πρέπει να βρούμε ποιά αεροπλάνα είναι πιο κοντά. Έτσι;

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

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

Φίλε και εγώ πάω γυμνάσιο και δεν κατάλαβα τίποτα!! Δεν καταλαβαίνω την διαφορά των δυο θεμάτων (Γυμνασίου και Λυκείου) . Ποιά είναι ρε παιδιά??

[chris]

ahm, δεν έχουν καμία σχέση... Εντελώς άλλα θέματα!
Πάντως στο δικό μας (του Γυμνασίου) εγώ κατάλαβα ότι πρέπει να κάνουμε ένα πρόγραμμα που σε έναν τρισδιάστατο πίνακα, θα βρίσκει τα δύο αεροπλάνα που είναι πιο κοντά το ένα με το άλλο. Οι θέσεις των αεροπλάνων θα δίνονται στο αρχείο εισόδου. Η πρώτη γραμμή με τον αριθμό N μας λέει πόσα αεροπλάνα υπάρχουν στο πεδίο μας. (Αυτό απλά κάνει την ανάγνωση του αρχείου πιο εύκολη, καθώς δεν πρέπει να ψάχνουμε για End of File) Οι υπόλοιπες Ν γραμμές έχουν τις συντεταγμές των αεροπλάνων.

Ας πούμε ότι έχουμε 3 αεροπλάνα Α,Β,Γ
Βρίσκουμε την απόσταση των Α-Β,Α-Γ,Β-Γ (ΔΕΝ ΕΧΩ ΙΔΕΑ ΠΩΣ!!!)
και μετά βρίσκουμε το ΜΑΧ και ΜΙΝ, πράγμα εύκολο.

Το πρόβλημα είναι πως βρίσκουμε την απόσταση δύο αντικειμένων σε έναν τρισδιάστατο χώρο!

[stathis]

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

Κάν'το μια μετάφραση στα Αγγλικά και θα καταλάβεις κατευθείαν.

[eparon]

δεν είναι πολύ δύσκολο να το βρείτε πάντως αυτό με την απόσταση και σας έχουν και μια υπόδειξη.
αποτελεί ένα σύνηθες (και απλό σχετικά) μαθηματικό πρόβλημα.
btw είναι και επίκαιρο το θέμα του γυμνασίου
άσε που ο αλγόριθμός σας μπορεί να τρέχει και σε κανένα pc στο πεντάγωνο μετά για αναχαίτηση αεροσκαφών

[kernelpanic]

Κι εγώ 3η Γυμνασίου

Υπάρχει ένα θεωρητικό bug, αν απόσταση μεταξύ 1-2 =ελάχιστο και 2-3 = επίσης ελάχιστο, τότε η λύση είναι 1-2 ή 2-3;

Τό'χω λύσει, τό χω λύσει, μένει ακόμη η υλοποίηση

[eparon]

kernelpanic, δεν υφίσταται το bug που λες... διάβασε καλύτερα την εκφώνηση...

Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο,
αφού διαβάσει τα δεδομένα της εξόδου ενός ψηφιακού ραντάρ, με τη μορφή
τριάδας δεδομένων που αντιστοιχούν σε κάθε εντοπισθέν ίχνος, θα εντοπίζει
και θα επισημαίνει τα ίχνη με τη μικρότερη μεταξύ τους απόσταση, άρα το
μεγαλύτερο κίνδυνο σύγκρουσης.

λέει τα ίχνη, που σημαίνει ότι είναι σίγουρα πάνω από ένα. άρα εσύ τα εμφανίζεις όσα και να είναι.

[georgeha98]

Δεν έχω δει το θέμα του Γυμνασίου, αλλά του Λυκείου είναι κλασσικό θέμα Shortest Path, δεν είναι δύσκολη η υλοποίησή του αλλά προφανώς θα δυσκολευτούμε λίγο με πολυπλοκότητα του αλγορίθμου.

[stathis]

Εγώ πάντως ακόμη δεν έχω κοιτάξει κανένα απ' τα δύο θέματα, χοχοχο.

ΥΓ: Σας παρακαλώ μην προχωράτε σε πολύ αποκαλυπτικές απαντήσεις σε σχέση με τις λύσεις, γιατί θα μας κράξουν.

[chris]

Εύρηκα, εύρηκα! Θα ασχοληθώ μαζί του το άλλο σαββατοκύριακο, αύριο γράφω Αρχαία...

[kernelpanic]

λέει τα ίχνη, που σημαίνει ότι είναι σίγουρα πάνω από ένα. άρα εσύ τα εμφανίζεις όσα και να είναι.

Αρχεία Εξόδου
Τα αρχεία εξόδου με όνομα airforce.out είναι αρχεία κειμένου με την εξής
δομή: Αποτελούνται από μια μόνο γραμμή που έχει δύο αριθμούς
χωριζόμενους με ένα κενό. Οι αύξοντες αριθμοί (θέσεις n-1, στο αρχείο
airforce.in) των ιχνών που έχουν τη μικρότερη απόσταση.

Δε νομίζω να βάλουν τλετοια περίπτωση, αλλά αν Α(1,1,1) και Β(1,1,2) και Γ(1,1,-1) , τότε γράφουμε διάνυσμα ΑΒ ή ΑΓ;
Ωχ, συγνώμη, λέει ότι δε θα δώσουν κάτι τέτοιο...

[Ελεύθεροσκοπευτής]

ρε ανθρωποι μια λεπτομέρεια...
που γράφει ποιοι δικαιούνται να δώσουν τον Β (πέρασαν);;;

μας στέλνουν κάποιο μέηλ που δεν έχω λάβει ή αναρτώνται πουθενά;;

[eparon]

θα σας στείλουν mail κατ αρχήν με τη βαθμολογία σας στην Α Φάση, και αν έχετε περάσει θα σας στείλουν και νέο mail με τα νέα στοιχεία σας για τον Talo

[chris]

Πάντως το έχω λύσει στο χαρτί, και θα το γράψω το σαββατοκύριακο! Δεν είναι και τόσο δύσκολο τελικά!

[kernelpanic]

Όταν λέει πως ο χρόνος υπολογισμού είναι ζωτικής σημασίας σημαίνει πως αν δε το γράψουμε με τον γρηγορότερο τρόπο χαθήκαμε;

[thelastnicholas]

Σημαίνει ότι σε περίπτωση ισοβαθμιών το πιο γρήγορο πρόγραμμα θα πάρει μεγαλύτερη βαθμολογία. Αν τα λύνει όλα σωστά θα περάσεις ακόμη και να κάνει 5 δευτερόλεπτα στο καθένα (αυτό νομίζω ότ είναι το όριο)

[chris]

Όχι. Απλά αν το δικό μου κάνει 2 sec, και το δικό σου 1, τότε εσύ παίρνεις καλύτερη βαθμολογία από εμένα, γιατί απλά είναι πιο γρήγορο. Βέβαια, κανένα δεν πρέπει να κάνει πάνω από 5 sec γιατί τότε παίρνουμε κουλουράκι.

[kernelpanic]

Πάντως αν παίρνει πάνω από δευτερόλεπτο σ'αυτό το σύστημα τότε σίγουρα υπάρχει σοβαρό πρόβλημα στον κώδικα

ΥΓ: Για κάθε αεροπλανάκι, είναι απαραίτητο οι συντεταγμένες του επομένου να είναι πάντα όλες μεγαλύτερες ή ίσες; Γιατί έτσι δείχνουν τα παραδείγματα...

[thetrojan01]

1. chris: κοίτα κάτω-κάτω στο θέμα. Λέει πως να βρεις την απόσταση σημείων σε 3D, αν εννοείς αυτό. Η σκέψη του είναι:

Spoiler: show

εφαρμόζεται το πυθαγόριο θεώρημα ανά άξονα. Έτσι έχουμε:
,,________________________________________
\/(χ1-χ2)^2 + (y1-y2)^2 + (z1-z2)^2

και ξέροντας (θεωρητικά - μάλλον δεν το σκέφτηκαν αυτό εκείνοι που έγραφαν το θέμα - ΝΑ ΣΕ ΚΑΛΑ ΚΥΡΙΕ ΜΑΘΗΜΑΤΙΚΕ ΜΟΥ!) οτι ρίζα(χ)= χ στην 1/2 έχουμε:
[ (χ1-χ2)^2 + (y1-y2)^2 + (z1-z2)^2 ] ^(1/2)

ή, επειδή οι γλώσσες μας (Pascal, C/C++) δεν έχουν αγγύλες, τα αντικαθιστάς όπως λέει η παρατήρηση 1 στο θέμα.

2.

Υπάρχει ένα θεωρητικό bug, αν απόσταση μεταξύ 1-2 =ελάχιστο και 2-3 = επίσης ελάχιστο, τότε η λύση είναι 1-2 ή 2-3;

Αν κατάλαβα καλά, δεν νομίζω γιατί λέει (βλ Παρατήρηση νο. 5) ότι δεν υπάρχουν περισσότερα από ένα ζεύγη αεροσκαφών με την ίδια μικρότερη απόσταση μεταξύ τους.

3. Έχω ένα πρόβλημα με την Παρατήρηση ν.4. Εννοεί ότι πρώτο θα μπεί το μικρότερο ID του αεροσκάφους και μετά το μεγαλύτερο; πχ. Πρώτο το αεροσκάφος ν. 40 και μετά το αεροσκάφος ν. 59 ?