χαου γουέρ δε θέματα φορ γιού??
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
χαου γουέρ δε θέματα φορ γιού??
απόψεις, λύσεις, ιδέες, αποτελέσματα...
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: χαου γουέρ δε θέματα φορ γιού??
Βασικά είμαι περίαργος να μάθω πόσοι έλυσαν και όλα ή τουλάχιστον δύο από τα τρία θέματα...
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: χαου γουέρ δε θέματα φορ γιού??
μέτρα έναν εμένα 3 στα 3
- compileGuy
- Δημοσιεύσεις: 218
- Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm
Re: χαου γουέρ δε θέματα φορ γιού??
Εγώ 1 στα 3 αν και πάλεψα το 2ο!!
Δεν πειραζει! Του χρόνου καλύτερα!!
Δεν πειραζει! Του χρόνου καλύτερα!!
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: χαου γουέρ δε θέματα φορ γιού??
0/3
στο πρώτο δε θυμώμουν πώς να χειριστώ τις long long int (fprintf & scanf)
προσπάθησα το 2ο αλλά ήθελα 1,5 λεπτό και θα το έλυνα! να πάρει μου τελείωσε ο χρόνος...
Έριξα μόνο μια ματιά στο cpu (3o) και είδα κάτι για ενώσεις και το παράτησα μην ήταν κάνας γράφος...
Δεν με πειράζει γιατί έχω ακόμη 4 χρόνια να προσπαθώ!...
Θα χαρώ να τα πούμε πάλι του χρόνου.
Αν το φόρουμ παραμείνει ανοιχτό, θα στείλω λύσεις (το πώς θα τα έλυνα αν είχα παραπάνω χρόνο και δε ξεχνούσα τη long long )
ήδη αρχίζω και τα ξανα(;)λύνω
στο πρώτο δε θυμώμουν πώς να χειριστώ τις long long int (fprintf & scanf)
προσπάθησα το 2ο αλλά ήθελα 1,5 λεπτό και θα το έλυνα! να πάρει μου τελείωσε ο χρόνος...
Έριξα μόνο μια ματιά στο cpu (3o) και είδα κάτι για ενώσεις και το παράτησα μην ήταν κάνας γράφος...
Δεν με πειράζει γιατί έχω ακόμη 4 χρόνια να προσπαθώ!...
Θα χαρώ να τα πούμε πάλι του χρόνου.
Αν το φόρουμ παραμείνει ανοιχτό, θα στείλω λύσεις (το πώς θα τα έλυνα αν είχα παραπάνω χρόνο και δε ξεχνούσα τη long long )
ήδη αρχίζω και τα ξανα(;)λύνω
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: χαου γουέρ δε θέματα φορ γιού??
1ο, 3ο, και 2ο on paper. Το 3ο μάλλον δε θα μετρήσει (σεγκμεντέησον έρρορ γμτ ), αν και μάλλον δούλεψε άνετα στο μηχάνημά μου
(Για όσους απορούν, το πρόβλημα με το 1ο ήταν το ότι το παραγοντικό ήταν πολύ μεγάλο και ξανάρχιζε απ'το μηδέν)
Πάω να ξεραθώ στον ύπνο τώρα, σας συμβουλέυω το ίδιο
(Για όσους απορούν, το πρόβλημα με το 1ο ήταν το ότι το παραγοντικό ήταν πολύ μεγάλο και ξανάρχιζε απ'το μηδέν)
Πάω να ξεραθώ στον ύπνο τώρα, σας συμβουλέυω το ίδιο
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: χαου γουέρ δε θέματα φορ γιού??
Πώς λύσατε το 3ο;
Re: χαου γουέρ δε θέματα φορ γιού??
Μια λύση (σχετικά απλή στην υλοποίηση της, κατά την άποψη μου) σε O(n^2), αν θυμάμαι καλά:
Φτιάχνουμε ένα διάγραμμα με όλες τις συσκευές στη σειρά, οριζοντίως. Από την πρώτη έως την τελευταία. Συνδέουμε την πρώτη με την τελευταία από πάνω και από κάτω (με καμπύλες). Έπειτα προσθέτουμε τις επιπλέον συνδέσεις, επίσης με καμπύλες· όταν μια σύνδεση δεν μπορεί να χαραχτεί από πάνω, προσπαθούμε να την κατασκευάσουμε από κάτω.
Κάθε συσκευή με αυτόν τον τρόπο βρίσκεται κάτω από κάποια καμπύλη, μερικές κάτω από μικρότερες καμπύλες, άλλες από μεγαλύτερες. Η καμπύλη που "περικλείει πιο στενά" μια συσκευή θα μας απασχολήσει. Για παράδειγμα, αν σε ένα κύκλωμα συσκευών με 5 συσκευές έχουμε τραβήξει τις συνδέσεις-καμπύλες 1-5 και 2-4, για τη συσκευή 3 μας απασχολεί η καμπύλη 2-4 και όχι η 1-5.
Με αυτό στο νου μας, μπορούμε να διατυπώσουμε τον κανόνα βάσει του οποίου αποφασίζουμε αν δυο συσκευές μπορούν να συνδεθούν: αν βρίσκονται και οι δύο κάτω από την ίδια καμπύλη και αυτή η καμπύλη είναι αυτή που "περικλείει πιο στενά" και τις δύο συσκευές (είτε από κάτω είτε από πάνω, είτε και από τις δύο πλευρές), τότε αυτή η σύνδεση είναι εφικτή.
Γνωρίζω ότι ο τρόπος εξήγησης (και επίλυσης) είναι μάλλον μπακαλίστικος. Αλλά αν ακολουθήσετε τις παραπάνω οδηγίες στο χαρτί, θα δείτε ότι δεν είναι διόλου ακαταλαβίστικος.
Φτιάχνουμε ένα διάγραμμα με όλες τις συσκευές στη σειρά, οριζοντίως. Από την πρώτη έως την τελευταία. Συνδέουμε την πρώτη με την τελευταία από πάνω και από κάτω (με καμπύλες). Έπειτα προσθέτουμε τις επιπλέον συνδέσεις, επίσης με καμπύλες· όταν μια σύνδεση δεν μπορεί να χαραχτεί από πάνω, προσπαθούμε να την κατασκευάσουμε από κάτω.
Κάθε συσκευή με αυτόν τον τρόπο βρίσκεται κάτω από κάποια καμπύλη, μερικές κάτω από μικρότερες καμπύλες, άλλες από μεγαλύτερες. Η καμπύλη που "περικλείει πιο στενά" μια συσκευή θα μας απασχολήσει. Για παράδειγμα, αν σε ένα κύκλωμα συσκευών με 5 συσκευές έχουμε τραβήξει τις συνδέσεις-καμπύλες 1-5 και 2-4, για τη συσκευή 3 μας απασχολεί η καμπύλη 2-4 και όχι η 1-5.
Με αυτό στο νου μας, μπορούμε να διατυπώσουμε τον κανόνα βάσει του οποίου αποφασίζουμε αν δυο συσκευές μπορούν να συνδεθούν: αν βρίσκονται και οι δύο κάτω από την ίδια καμπύλη και αυτή η καμπύλη είναι αυτή που "περικλείει πιο στενά" και τις δύο συσκευές (είτε από κάτω είτε από πάνω, είτε και από τις δύο πλευρές), τότε αυτή η σύνδεση είναι εφικτή.
Γνωρίζω ότι ο τρόπος εξήγησης (και επίλυσης) είναι μάλλον μπακαλίστικος. Αλλά αν ακολουθήσετε τις παραπάνω οδηγίες στο χαρτί, θα δείτε ότι δεν είναι διόλου ακαταλαβίστικος.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: χαου γουέρ δε θέματα φορ γιού??
Η δικιά μου υλοποίηση, της ίδιας ιδέας:
Αν ένα σημείο βρίσκεται κάτω από ΔΥΟ διανύσματα(τρόπος του λέγειν), τότε δε συνδέεται πουθενά.
Οπότε μετράμε το δακτύλιο, απ'τη μια ως την άλλη, και μαρκάρουμε τα σημεία του δακτυλίου +1 προσέχοντας έτσι ώστε να μη σημαδέψουμε την αρχή κ το τέλος.
ή
φορ(;(αρχη-1);--αρχη){ιφ(δακτύλιος[αρχη%κομβοι]<2) δακτυλιος[αρχη%κομβοι]++;ελσε{προβλημα=τρου;μπρέικ;}
ΥΓ. Η ΕΠΙΚΡΑΤΗΣΗ ΤΗΣ ΠΕΡΙΓΡΑΦΗΣ ΚΩΔΙΚΑ Η/ΚΑΙ ΟΡΩΝ ΥΠΟΛΟΓΙΣΤΩΝ ΜΕ ΕΛΛΗΝΙΚΑ ΓΡΑΜΜΑΤΑ
Η ΑΛΛΙΩΣ
ΙΝΤΕΡΝΈΤ ΣΑΝΤΟΥΊΤΣ ΚΟΡΚΟΤΟ
ΕΧΕΙ ΜΟΛΙΣ ΑΡΧΙΣΕΙ
Αν ένα σημείο βρίσκεται κάτω από ΔΥΟ διανύσματα(τρόπος του λέγειν), τότε δε συνδέεται πουθενά.
Οπότε μετράμε το δακτύλιο, απ'τη μια ως την άλλη, και μαρκάρουμε τα σημεία του δακτυλίου +1 προσέχοντας έτσι ώστε να μη σημαδέψουμε την αρχή κ το τέλος.
ή
φορ(;(αρχη-1);--αρχη){ιφ(δακτύλιος[αρχη%κομβοι]<2) δακτυλιος[αρχη%κομβοι]++;ελσε{προβλημα=τρου;μπρέικ;}
ΥΓ. Η ΕΠΙΚΡΑΤΗΣΗ ΤΗΣ ΠΕΡΙΓΡΑΦΗΣ ΚΩΔΙΚΑ Η/ΚΑΙ ΟΡΩΝ ΥΠΟΛΟΓΙΣΤΩΝ ΜΕ ΕΛΛΗΝΙΚΑ ΓΡΑΜΜΑΤΑ
Η ΑΛΛΙΩΣ
ΙΝΤΕΡΝΈΤ ΣΑΝΤΟΥΊΤΣ ΚΟΡΚΟΤΟ
ΕΧΕΙ ΜΟΛΙΣ ΑΡΧΙΣΕΙ
Τελευταία επεξεργασία από το μέλος kernelpanic την Δευ Απρ 13, 2009 8:58 pm, έχει επεξεργασθεί 1 φορά συνολικά.
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: χαου γουέρ δε θέματα φορ γιού??
Μόνο οι πρώτοι δέκα περνάνε? Στέλνουν ε-μαιλ σε όσουν πέρασαν? Δεν ξέρω αν το είδατε αλλά βγήκαν τα αποτελέσματα.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: χαου γουέρ δε θέματα φορ γιού??
Δεν έχει λινκ...
τη σύνθεση της ντριμ τιμ θα την αποφασίσουν μετά το καμπ, οπότε μην ανησυχείς
τη σύνθεση της ντριμ τιμ θα την αποφασίσουν μετά το καμπ, οπότε μην ανησυχείς
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: χαου γουέρ δε θέματα φορ γιού??
Και ποιοί θα πάνε στο καμπ εννοώ? Οι πρώτοι 8-10??
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: χαου γουέρ δε θέματα φορ γιού??
Μάλλον όλοι...
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: χαου γουέρ δε θέματα φορ γιού??
Οι 8-12 πρώτοι.
- kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: χαου γουέρ δε θέματα φορ γιού??
Από Λύκειο και Γυμνάσιο χωριστά;
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: χαου γουέρ δε θέματα φορ γιού??
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 και μορφοποίησε εξωτ.πίνακα σύμφωνα με το σκεπτικό πιο πάνω
αλλιώςαν τερμάτησε τη διαδικασία}
τύπωσε σύνολο
αα, όσων αφορά στο 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 και μορφοποίησε εξωτ.πίνακα σύμφωνα με το σκεπτικό πιο πάνω
αλλιώςαν τερμάτησε τη διαδικασία}
τύπωσε σύνολο
Re: χαου γουέρ δε θέματα φορ γιού??
Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: χαου γουέρ δε θέματα φορ γιού??
ε, προφανώς ήταν ο λόγος που έβγαλα 12.5/45 στο 3ο, αλλά ακούγεται καλύτερο απ' ότι 0/45, οπότε, δεν πα να ναι μεγάλο... με το που μου τη δέχτηκαν τη λύση είπε το παιδί από μπροστά οτί έκλεισαν οι υποβολές... (και χρειαζόταν και προηγουμένως τρελό αντι-μπάγκινγκ)userresu έγραψε:Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος