Hellenico Training Contest #2

Ελληνικοί διαγωνισμοί για τα παιδιά του ΠΔΠ.
feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest #2

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

Κι εμείς σας ευχαριστούμε πολύ για τα ενθαρρυντικά σας σχόλια. Άνευ απροόπτου θα το επαναλάβουμε τον επόμενο μήνα με νέο juicy problemset!

btw,
kernelpanic έγραψε:@compileguy:
Ποιό είναι το μέγιστο βάθος της αναδρομικής κλήσης; Νομίζω στα περίπου 2ΜΒ στοίβας καίγεσαι ;)

Κώδικας: Επιλογή όλων

grader@hellenico:~$ ulimit -s
8192

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

Re: Hellenico Training Contest #2

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

@chris:

1) 300.000 ακμές * 2 κατευθύνσεις * 4 sizeof(int) = 4.800.000 bytes.
2) για το frog:
Έστω η ακολουθία Α Κ όρων, όπου Αν το μήκος του κάθε βήματος.
Αφού το κόστος ενός άλματος εξαρτάται μόνο από το μήκος του, και το ολικό μήκος είναι το άθροισμα των όρων της Α (ισχύει η αντιμεταθετική ιδιότητα), τα άλματα-όροι της Α μπορούν να έχουν οποιαδήποτε σειρά μεταξύ τους.

Έστω λοιπόν οτι Κ(όστος)=Σ(ούμα των τετραγώνων όλων των όρων εκτός από Αν, Αξ)+Αν2ξ2.
Έστω μ=Αν+ Αξ,τ=μ div 2.

Αν μ ζυγός, ισχύει
Αν=τ+ρ
Αξ=τ-ρ
ρ ε Ν, ρ<=τ.

Τώρα,
Αν2=(τ+ρ)22+2τρ+ρ2,
Αξ2=(τ-ρ)22-2τρ+ρ2,
Αν2ξ2=2τ2+2ρ2

Όπως καταλαβαίνεις, συμφέρει το ρ=0(αφού γίνεται).

Τώρα για μ μονό είναι

Αν=τ+ρ+1
Αξ=τ-ρ
ρ ε Ν, |ρ|<=τ.

Οπότε

Αν2=(τ+ρ+1)22+2τρ+ρ2+2(τ+ρ)+1,
Αξ2=(τ-ρ)22-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.

feedWARd
Δημοσιεύσεις: 72
Εγγραφή: Κυρ Δεκ 21, 2008 3:32 pm

Re: Hellenico Training Contest #2

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

Tα testcases του διαγωνισμού. Στο apple το καθενα εχει αξια 10 βαθμων. Στα υπολοιπα 3 το καθενα εχει αξια 10 βαθμων εκτος απο αυτα που υπαρχουν στην εκφωνηση τα οποια δεν δινουν βαθμους.

Απάντηση