pdp forum

απόψεις, λύσεις, ιδέες, αποτελέσματα...

Βασικά είμαι περίαργος να μάθω πόσοι έλυσαν και όλα ή τουλάχιστον δύο από τα τρία θέματα...

μέτρα έναν εμένα 3 στα 3

Εγώ 1 στα 3 αν και πάλεψα το 2ο!!

Δεν πειραζει! Του χρόνου καλύτερα!!

3/3

0/3

στο πρώτο δε θυμώμουν πώς να χειριστώ τις long long int (fprintf & scanf)

προσπάθησα το 2ο αλλά ήθελα 1,5 λεπτό και θα το έλυνα! να πάρει μου τελείωσε ο χρόνος...
Έριξα μόνο μια ματιά στο cpu (3o) και είδα κάτι για ενώσεις και το παράτησα μην ήταν κάνας γράφος...

Δεν με πειράζει γιατί έχω ακόμη 4 χρόνια να προσπαθώ!...

Θα χαρώ να τα πούμε πάλι του χρόνου.



Αν το φόρουμ παραμείνει ανοιχτό, θα στείλω λύσεις (το πώς θα τα έλυνα αν είχα παραπάνω χρόνο και δε ξεχνούσα τη long long )

ήδη αρχίζω και τα ξανα(;)λύνω

1ο, 3ο, και 2ο on paper. Το 3ο μάλλον δε θα μετρήσει (σεγκμεντέησον έρρορ γμτ ), αν και μάλλον δούλεψε άνετα στο μηχάνημά μου

(Για όσους απορούν, το πρόβλημα με το 1ο ήταν το ότι το παραγοντικό ήταν πολύ μεγάλο και ξανάρχιζε απ'το μηδέν)

Πάω να ξεραθώ στον ύπνο τώρα, σας συμβουλέυω το ίδιο

Πώς λύσατε το 3ο;

Μια λύση (σχετικά απλή στην υλοποίηση της, κατά την άποψη μου) σε O(n^2), αν θυμάμαι καλά:

Φτιάχνουμε ένα διάγραμμα με όλες τις συσκευές στη σειρά, οριζοντίως. Από την πρώτη έως την τελευταία. Συνδέουμε την πρώτη με την τελευταία από πάνω και από κάτω (με καμπύλες). Έπειτα προσθέτουμε τις επιπλέον συνδέσεις, επίσης με καμπύλες· όταν μια σύνδεση δεν μπορεί να χαραχτεί από πάνω, προσπαθούμε να την κατασκευάσουμε από κάτω.

Κάθε συσκευή με αυτόν τον τρόπο βρίσκεται κάτω από κάποια καμπύλη, μερικές κάτω από μικρότερες καμπύλες, άλλες από μεγαλύτερες. Η καμπύλη που "περικλείει πιο στενά" μια συσκευή θα μας απασχολήσει. Για παράδειγμα, αν σε ένα κύκλωμα συσκευών με 5 συσκευές έχουμε τραβήξει τις συνδέσεις-καμπύλες 1-5 και 2-4, για τη συσκευή 3 μας απασχολεί η καμπύλη 2-4 και όχι η 1-5.

Με αυτό στο νου μας, μπορούμε να διατυπώσουμε τον κανόνα βάσει του οποίου αποφασίζουμε αν δυο συσκευές μπορούν να συνδεθούν: αν βρίσκονται και οι δύο κάτω από την ίδια καμπύλη και αυτή η καμπύλη είναι αυτή που "περικλείει πιο στενά" και τις δύο συσκευές (είτε από κάτω είτε από πάνω, είτε και από τις δύο πλευρές), τότε αυτή η σύνδεση είναι εφικτή.

Γνωρίζω ότι ο τρόπος εξήγησης (και επίλυσης) είναι μάλλον μπακαλίστικος. Αλλά αν ακολουθήσετε τις παραπάνω οδηγίες στο χαρτί, θα δείτε ότι δεν είναι διόλου ακαταλαβίστικος.

Η δικιά μου υλοποίηση, της ίδιας ιδέας:
Αν ένα σημείο βρίσκεται κάτω από ΔΥΟ διανύσματα(τρόπος του λέγειν), τότε δε συνδέεται πουθενά.
Οπότε μετράμε το δακτύλιο, απ'τη μια ως την άλλη, και μαρκάρουμε τα σημεία του δακτυλίου +1 προσέχοντας έτσι ώστε να μη σημαδέψουμε την αρχή κ το τέλος.
ή
φορ(;(αρχη-1);--αρχη){ιφ(δακτύλιος[αρχη%κομβοι]<2) δακτυλιος[αρχη%κομβοι]++;ελσε{προβλημα=τρου;μπρέικ;}

ΥΓ. Η ΕΠΙΚΡΑΤΗΣΗ ΤΗΣ ΠΕΡΙΓΡΑΦΗΣ ΚΩΔΙΚΑ Η/ΚΑΙ ΟΡΩΝ ΥΠΟΛΟΓΙΣΤΩΝ ΜΕ ΕΛΛΗΝΙΚΑ ΓΡΑΜΜΑΤΑ
Η ΑΛΛΙΩΣ
ΙΝΤΕΡΝΈΤ ΣΑΝΤΟΥΊΤΣ ΚΟΡΚΟΤΟ
ΕΧΕΙ ΜΟΛΙΣ ΑΡΧΙΣΕΙ

Μόνο οι πρώτοι δέκα περνάνε? Στέλνουν ε-μαιλ σε όσουν πέρασαν? Δεν ξέρω αν το είδατε αλλά βγήκαν τα αποτελέσματα.

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

Και ποιοί θα πάνε στο καμπ εννοώ? Οι πρώτοι 8-10??

Μάλλον όλοι...

Οι 8-12 πρώτοι.

Από Λύκειο και Γυμνάσιο χωριστά;

7ος, κατι ειν κ αυτό.... πότε παίρνουμε αναλυτική βαθμολογία;;;

αα, όσων αφορά στο 3ο θέμα... υπήρχε και ένας αρκετά ευκολότερος τρόπος λύσης...
με 2 πίνακες ΝχΝ
διαχώρησα τις ενώσεις σε εσωτερικές και εξωτερικές και θεώρησα χωρίς βλάβη της γενικότητος οτί 2 δεδομένα σημεία Κ1 Κ2 θα επιχειρήσει κανείς να τα ενώσει αρχικά εσωτερικά (εντός της βασικής συνδεσμολογίας) και άμα δεν βγεί, εκτός...
τώρα, κάθε ένας από τους δύο πίνακες είχε στήλες, σειρές τις συνδέσεις Κ, άμα το στοιχείο α[κ][λ] είναι 0, δεν μπορεί να γίνει σύνδεση, ενώ άμα είναι 1, επιτυγχάνεται....
σαφώς εξ ορισμού, σύμφωνα με τη βασική συνδεσμολογία, αρχικά και οι 2 πίνακες είχαν μόνο άσσους (οκ, να ενώσεις το 3 με το 3 π.χ. δεν έχει νόημα, αλλά εδν ζητήται και στην τελική)
στη συνέχεια κάθε σύνδεση μεταξύ των Α, Β (εσωτερική ή εξωτερική) εμποδίζει τις συνδέσεις που το ένα άκρο τους βρίσκεται (αριθμητικά) ανάμεσα στα Α,Β με ένα εξωτερικό (κάθε φορά αποκλειστικά για εσωτερική ή εξωτερική σύνδεση αντιστοίχως)
δηλαδή προκύπτει σχηματικά ο πίνακας:

_|_|_|_|_|Α|_|_|_|Β|_|
_|1|1|1|1|1|0|0|0|1|1|
_|1|1|1|1|1|0|0|0|1|1|
_|1|1|1|1|1|0|0|0|1|1|
_|1|1|1|1|1|0|0|0|1|1|
Α|1|1|1|1|1|0|0|0|1|1|
_|0|0|0|0|0|1|1|1|0|0|
_|0|0|0|0|0|1|1|1|0|0|
_|0|0|0|0|0|1|1|1|0|0|
Β|1|1|1|1|1|0|0|0|1|1|
_|1|1|1|1|1|0|0|0|1|1|

και ο αλγόριθμος είναι ουσιαστικά:

Διάβασε αριθμό ενώσεων Ν
Δημιούργησε 2 πίνακες ΝχΝ (εσωτ.-εξωτ.) οπού κάθε στοιχείο είναι το 1
Διάβασε αριθμό ζευγών Κ
Διάβασε Κ διαφορετικά ζεύγη Ακ, Βκ
Αν σε οποιοδήποτε ζεύγος είναι Ακ>Βκ άλλαξέ τους διάταξη (χρειάζεται στο τέλος, για να μην μπλέκω με μόντουλα)
Επανέλλαβε Κ φορές:
{αν εσωτ(Ακ, Βκ)==1, σύνολο+1 και μορφοποίησε εσωτ.πίνακα σύμφωνα με το σκεπτικό πιο πάνω
αλλιώςαν εξωτ(Ακ,Βκ)==1, σύνολο+1 και μορφοποίησε εξωτ.πίνακα σύμφωνα με το σκεπτικό πιο πάνω
αλλιώςαν τερμάτησε τη διαδικασία}
τύπωσε σύνολο

Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος

userresu έγραψε:Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος

ε, προφανώς ήταν ο λόγος που έβγαλα 12.5/45 στο 3ο, αλλά ακούγεται καλύτερο απ' ότι 0/45, οπότε, δεν πα να ναι μεγάλο... με το που μου τη δέχτηκαν τη λύση είπε το παιδί από μπροστά οτί έκλεισαν οι υποβολές... (και χρειαζόταν και προηγουμένως τρελό αντι-μπάγκινγκ)