χαου γουέρ δε θέματα φορ γιού??

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

χαου γουέρ δε θέματα φορ γιού??

Δημοσίευση από Ελεύθεροσκοπευτής »

απόψεις, λύσεις, ιδέες, αποτελέσματα... :roll:
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

Βασικά είμαι περίαργος να μάθω πόσοι έλυσαν και όλα ή τουλάχιστον δύο από τα τρία θέματα...
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

Re: χαου γουέρ δε θέματα φορ γιού??

Δημοσίευση από Ελεύθεροσκοπευτής »

μέτρα έναν εμένα 3 στα 3 :D :D
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

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

Δεν πειραζει! Του χρόνου καλύτερα!! ;)
Quajafrie
Δημοσιεύσεις: 8
Εγγραφή: Δευ Απρ 13, 2009 5:30 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

3/3
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

0/3

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

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

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

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



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

ήδη αρχίζω και τα ξανα(;)λύνω
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: χαου γουέρ δε θέματα φορ γιού??

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

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

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

Πάω να ξεραθώ στον ύπνο τώρα, σας συμβουλέυω το ίδιο ;)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

Πώς λύσατε το 3ο;
Quajafrie
Δημοσιεύσεις: 8
Εγγραφή: Δευ Απρ 13, 2009 5:30 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

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

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

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

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

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

Re: χαου γουέρ δε θέματα φορ γιού??

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

Η δικιά μου υλοποίηση, της ίδιας ιδέας:
Αν ένα σημείο βρίσκεται κάτω από ΔΥΟ διανύσματα(τρόπος του λέγειν), τότε δε συνδέεται πουθενά.
Οπότε μετράμε το δακτύλιο, απ'τη μια ως την άλλη, και μαρκάρουμε τα σημεία του δακτυλίου +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.
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

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

Re: χαου γουέρ δε θέματα φορ γιού??

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

Δεν έχει λινκ...
τη σύνθεση της ντριμ τιμ θα την αποφασίσουν μετά το καμπ, οπότε μην ανησυχείς ;)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

Και ποιοί θα πάνε στο καμπ εννοώ? Οι πρώτοι 8-10??
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: χαου γουέρ δε θέματα φορ γιού??

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

Μάλλον όλοι... ;)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

Οι 8-12 πρώτοι.
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: χαου γουέρ δε θέματα φορ γιού??

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

Από Λύκειο και Γυμνάσιο χωριστά;
99 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 και μορφοποίησε εξωτ.πίνακα σύμφωνα με το σκεπτικό πιο πάνω
αλλιώςαν τερμάτησε τη διαδικασία}
τύπωσε σύνολο
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: χαου γουέρ δε θέματα φορ γιού??

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

Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος :P
Ελεύθεροσκοπευτής
Δημοσιεύσεις: 33
Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am

Re: χαου γουέρ δε θέματα φορ γιού??

Δημοσίευση από Ελεύθεροσκοπευτής »

userresu έγραψε:Δεδομένου ότι το Ν φτάνει μέχρι 200.000, ένας πίνακας int με N^2 στοιχεία (160000000000 bytes) είναι λίιιιγο μεγάλος :P
ε, προφανώς ήταν ο λόγος που έβγαλα 12.5/45 στο 3ο, αλλά ακούγεται καλύτερο απ' ότι 0/45, οπότε, δεν πα να ναι μεγάλο... με το που μου τη δέχτηκαν τη λύση είπε το παιδί από μπροστά οτί έκλεισαν οι υποβολές... (και χρειαζόταν και προηγουμένως τρελό αντι-μπάγκινγκ)
Απάντηση