Euler Competition 2016/2

#1

Ένα υποβρύχιο κινείται σε μια ευθεία γραμμή με τύπο p(t) = at+b

όπου

είναι ο χρόνος και p(t)

η θέση του υποβρυχίου. Στόχος είναι να βυθίσετε το υποβρύχιο το οποίο όμως δεν μπορείτε να δείτε αφού βρίσκεται κάτω από το νερό.

Οι συντελεστές a,b

είναι άγνωστοι σε εσάς ακέραιοι. Σε κάθε χρονική στιγμή

, όπου ο

είναι θετικός ακέραιος, μπορείτε να πυροβολήσετε οποιοδήποτε ακέραιο σημείο. Αν το υποβρύχιο βρίσκεται σε αυτό το σημείο, τότε το βυθίζετε.

Να βρείτε αλγόριθμο που εγγυάται εν τέλει την βύθιση του υποβρυχίου.

dement · #2

Υποθέτω ότι βρισκόμαστε σε

διαστάσεις.

Έστω $f: \mathbb{N}^* \to \mathbb{Z}^d \times \mathbb{Z}^d$ αρίθμηση του $\mathbb{Z}^d \times \mathbb{Z}^d$ . Oρίζουμε ακολουθίες (a_n), (b_n)

έτσι ώστε

.

Σε κάθε χρονική στιγμή

χτυπάμε στο n a_n + b_n

. Το υποβρύχιο θα βυθιστεί το πολύ τη στιγμή $m = f^{-1} \left[ (a,b) \right]$ .

(Προφανώς δουλεύει και με ρητούς a, b

αντί για ακέραιους).

Υ.Γ. Όπως μου επιβεβαίωσε ο Δ. Χριστοφίδης, το πρόβλημα αναφέρεται στην ειδική περίπτωση d = 1

.

Euler Competition 2016/2

Euler Competition 2016/2

Re: Euler Competition 2016/2

Μέλη σε σύνδεση