[Codility] Μάθημα-04.1: FrogRiverOne

Αυτή η ανάρτηση χειρίζεται την πρώτη λύση του μαθήματος 4 χρησιμοποιώντας python. Το θέμα του μαθήματος 4 είναι τα «Στοιχεία μέτρησης». Για πρόσβαση στο πρόβλημα, κάντε κλικ στον παρακάτω σύνδεσμο.

Περιγραφή των εργασιών

Ένας μικρός βάτραχος θέλει να φτάσει στην άλλη πλευρά ενός ποταμού. Ο βάτραχος βρίσκεται αρχικά σε μια όχθη του ποταμού (θέση 0) και θέλει να φτάσει στην απέναντι όχθη (θέση Χ+1). Τα φύλλα πέφτουν από ένα δέντρο στην επιφάνεια του ποταμού.

Σας δίνεται ένας πίνακας Α που αποτελείται από N ακέραιους αριθμούς που αντιπροσωπεύουν τα φύλλα που πέφτουν. Το A[K] αντιπροσωπεύει τη θέση όπου ένα φύλλο πέφτει τη στιγμή K, μετρούμενη σε δευτερόλεπτα.

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

Για παράδειγμα, σας δίνεται ακέραιος X = 5 και ο πίνακας A έτσι ώστε:

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

Στο δεύτερο 6, ένα φύλλο πέφτει στη θέση 5. Αυτή είναι η πρώτη φορά που εμφανίζονται φύλλα σε κάθε θέση πέρα ​​από τον ποταμό.

Γράψτε μια συνάρτηση:

def λύση (X, A)

ότι, δεδομένου ενός μη κενού πίνακα Α που αποτελείται από N ακέραιους και ακέραιο X, επιστρέφει τον πρώιμο χρόνο που ο βάτραχος μπορεί να πηδήξει στην άλλη πλευρά του ποταμού.

Εάν ο βάτραχος δεν μπορεί ποτέ να πηδήξει στην άλλη πλευρά του ποταμού, η συνάρτηση θα πρέπει να επιστρέψει −1.

Για παράδειγμα, δίνεται X = 5 και πίνακας A έτσι ώστε:

A[0] = 1

A[1] = 3

A[2] = 1

A[3] = 4

A[4] = 2

A[5] = 3

A[6] = 5

A[7] = 4

η συνάρτηση θα πρέπει να επιστρέψει 6, όπως εξηγήθηκε παραπάνω.

Γράψτε έναν αποδοτικό αλγόριθμο για τις ακόλουθες παραδοχές:

• Τα N και X είναι ακέραιοι εντός της περιοχής [1..100.000].
• κάθε στοιχείο του πίνακα Α είναι ένας ακέραιος στην περιοχή [1..X].

Πνευματικά δικαιώματα 2009–2020 από την Codility Limited. Ολα τα δικαιώματα διατηρούνται. Απαγορεύεται η μη εξουσιοδοτημένη αντιγραφή, δημοσίευση ή αποκάλυψη.

Σημείο κλειδί

• Έχετε ήδη μάθει πώς να έχετε αποτελεσματικότητα στην επίλυση προβλημάτων.
• Επίσης, μπορείτε να μετρήσετε το στοιχείο μέσω ενός απλού και ισχυρού αλγορίθμου γραμμικής αναζήτησης.

Λύση (με χρήση Python)

def solution(X, A):
    leaf_check, sum_step = [False] * X, 0
    for sec, fall in enumerate(A):
        if(fall > X): continue
        if(not(leaf_check[fall-1])):
            leaf_check[fall-1] = True
            sum_step += 1
            if(sum_step == X): return sec
    return -1

Χρησιμοποιήστε την παραπάνω λύση για αναφορά.
Σας συνιστούμε να γράψετε τον δικό σας πηγαίο κώδικα.

Σχετική ανάρτηση