btw,
kernelpanic έγραψε:@compileguy:
Ποιό είναι το μέγιστο βάθος της αναδρομικής κλήσης; Νομίζω στα περίπου 2ΜΒ στοίβας καίγεσαι
Κώδικας: Επιλογή όλων
grader@hellenico:~$ ulimit -s
8192Hellenico Training Contest #2
Re: Hellenico Training Contest #2
Κι εμείς σας ευχαριστούμε πολύ για τα ενθαρρυντικά σας σχόλια. Άνευ απροόπτου θα το επαναλάβουμε τον επόμενο μήνα με νέο juicy problemset!
btw,
btw,
-
kernelpanic
- Δημοσιεύσεις: 404
- Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
- Τοποθεσία: Αθήνα
Re: Hellenico Training Contest #2
@chris:
1) 300.000 ακμές * 2 κατευθύνσεις * 4 sizeof(int) = 4.800.000 bytes.
2) για το frog:
Έστω η ακολουθία Α Κ όρων, όπου Αν το μήκος του κάθε βήματος.
Αφού το κόστος ενός άλματος εξαρτάται μόνο από το μήκος του, και το ολικό μήκος είναι το άθροισμα των όρων της Α (ισχύει η αντιμεταθετική ιδιότητα), τα άλματα-όροι της Α μπορούν να έχουν οποιαδήποτε σειρά μεταξύ τους.
Έστω λοιπόν οτι Κ(όστος)=Σ(ούμα των τετραγώνων όλων των όρων εκτός από Αν, Αξ)+Αν2+Αξ2.
Έστω μ=Αν+ Αξ,τ=μ div 2.
Αν μ ζυγός, ισχύει
Αν=τ+ρ
Αξ=τ-ρ
ρ ε Ν, ρ<=τ.
Τώρα,
Αν2=(τ+ρ)2=τ2+2τρ+ρ2,
Αξ2=(τ-ρ)2=τ2-2τρ+ρ2,
Αν2+Αξ2=2τ2+2ρ2
Όπως καταλαβαίνεις, συμφέρει το ρ=0(αφού γίνεται).
Τώρα για μ μονό είναι
Αν=τ+ρ+1
Αξ=τ-ρ
ρ ε Ν, |ρ|<=τ.
Οπότε
Αν2=(τ+ρ+1)2=τ2+2τρ+ρ2+2(τ+ρ)+1,
Αξ2=(τ-ρ)2=τ2-2τρ+ρ2,
Αν2+Αξ2=2τ2+2ρ2+2(τ+ρ)+1
πάλι συμφέρει το ρ=0.
Κατ' επέκτασιν(αφού οι όροι είναι πλήρως εναλλάξιμοι) πρέπει
|Αν-Αξ|<=1 για κάθε ν != ξ στην ακολουθία.
Για να γίνει η κατανομή αποστάσεως στα βήματα ένας τρόπος είναι:
(Ν-1 mod K) μεγάλα άλματα μήκους (N-1 div K)+1
(K-(Ν-1 mod K)) μικρά άλματα μήκους (N-1 div K)
(Αφαιρούμε 1 από το Ν της εκφώνησης γιατί ξεκινάμε από τη θέση 1 άρα απόσταση=Ν-1)
Θυμήσου να χρησιμοποιήσεις 64bitους ακεραίους γιατί το αποτέλεσμα μπορεί να γίνει πολύ μεγάλο.
ΥΓ: Υπάρχει και πιο σύντομος τρόπος απόδειξης αν έχεις υποπτευθεί την τέλεια ακολουθία
1) 300.000 ακμές * 2 κατευθύνσεις * 4 sizeof(int) = 4.800.000 bytes.
2) για το frog:
Έστω η ακολουθία Α Κ όρων, όπου Αν το μήκος του κάθε βήματος.
Αφού το κόστος ενός άλματος εξαρτάται μόνο από το μήκος του, και το ολικό μήκος είναι το άθροισμα των όρων της Α (ισχύει η αντιμεταθετική ιδιότητα), τα άλματα-όροι της Α μπορούν να έχουν οποιαδήποτε σειρά μεταξύ τους.
Έστω λοιπόν οτι Κ(όστος)=Σ(ούμα των τετραγώνων όλων των όρων εκτός από Αν, Αξ)+Αν2+Αξ2.
Έστω μ=Αν+ Αξ,τ=μ div 2.
Αν μ ζυγός, ισχύει
Αν=τ+ρ
Αξ=τ-ρ
ρ ε Ν, ρ<=τ.
Τώρα,
Αν2=(τ+ρ)2=τ2+2τρ+ρ2,
Αξ2=(τ-ρ)2=τ2-2τρ+ρ2,
Αν2+Αξ2=2τ2+2ρ2
Όπως καταλαβαίνεις, συμφέρει το ρ=0(αφού γίνεται).
Τώρα για μ μονό είναι
Αν=τ+ρ+1
Αξ=τ-ρ
ρ ε Ν, |ρ|<=τ.
Οπότε
Αν2=(τ+ρ+1)2=τ2+2τρ+ρ2+2(τ+ρ)+1,
Αξ2=(τ-ρ)2=τ2-2τρ+ρ2,
Αν2+Αξ2=2τ2+2ρ2+2(τ+ρ)+1
πάλι συμφέρει το ρ=0.
Κατ' επέκτασιν(αφού οι όροι είναι πλήρως εναλλάξιμοι) πρέπει
|Αν-Αξ|<=1 για κάθε ν != ξ στην ακολουθία.
Για να γίνει η κατανομή αποστάσεως στα βήματα ένας τρόπος είναι:
(Ν-1 mod K) μεγάλα άλματα μήκους (N-1 div K)+1
(K-(Ν-1 mod K)) μικρά άλματα μήκους (N-1 div K)
(Αφαιρούμε 1 από το Ν της εκφώνησης γιατί ξεκινάμε από τη θέση 1 άρα απόσταση=Ν-1)
Θυμήσου να χρησιμοποιήσεις 64bitους ακεραίους γιατί το αποτέλεσμα μπορεί να γίνει πολύ μεγάλο.
ΥΓ: Υπάρχει και πιο σύντομος τρόπος απόδειξης αν έχεις υποπτευθεί την τέλεια ακολουθία
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: Hellenico Training Contest #2
Tα testcases του διαγωνισμού. Στο apple το καθενα εχει αξια 10 βαθμων. Στα υπολοιπα 3 το καθενα εχει αξια 10 βαθμων εκτος απο αυτα που υπαρχουν στην εκφωνηση τα οποια δεν δινουν βαθμους.
