zadanie z rybkami

0

siemaneczko
zadanie wygląda tak:
dostaje się dwie listy A i B
A reprezentuje wielkość danej rybki
B kierunek poruszania się rybki (0 - w górę strumienia, 1 - w dół)
jeżeli rybki się ze soba spotkają tzn. jedna wpłynie na drugą to większa pożera mniejszą.
ryby poruszaja się z ta samą predkością czyli jak jedna porusza się w dół strumienia i ta za nią też , to te rybki się nie spotkają.
program ma zwrócić ile rybek zostanie przy zyciu:
np dla:
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
program ma zwrócić 2 bo przeżyje rybka pierwsza i ostatnia
pomocy!
złożność O(N) N = len(A)

0

Co się dzieje gdy spotkają się rybki tej samej wielkości?
Jakie jest położenie początkowe rybek?

0

Początkowe położenie rybek jest takie same jak indeksy:

A[0] = 4 B[0] = 0 # Ta rybka płynie do góry więc jest bezpieczna
A[1] = 3 B[1] = 1 # Ta płynie w dół więc napotka te poniżej płynące do góry
A[2] = 2 B[2] = 0 # Zostanie zjedzona przez A[1]
A[3] = 1 B[3] = 0 # Zostanie zjedzona przez A[1]
A[4] = 5 B[4] = 0 # Jako że ta rybka jest większa zje rybkę A[1]
0

Każda rybka ma inną wielkość

0

mi chodzi o to aby rozwiązanie zapiać w pythonie tak aby działało dla dowolnych list A i B :)

0

Złożoności O(n) jesteś pewien?

0
bogdans napisał(a):

Złożoności O(n) jesteś pewien?

Intuicja mówi mi, że się da. :)

0

dostałem takie zadanko na portalu któremu ufam .... ale z tą złożonością to raczej z przymrueniem oka

0

To może poszukać największych ryb płynących w górę i w dół, i sprawdzić ile zjedzą tych co płyną w przeciwnym kierunku? Uwzględnij fakt że jedna z nich będzie większa, i zje tą drugą uniemożliwiając jej dalszą konsumpcję.

edit: no chyba że ta co płynie w górę będzie wyżej niż ta co płynie w dół, wtedy trzeba będzie powtórzyć wszystko dla rybek między nimi.

0

ale jak to zapisać?

0

O(n^2) Cię urządza?

0

dawaj jak masz :)

0
while True:
    found = False
    for i in range(len(B) - 1):
        if B[i] == 1 and B[i + 1] == 0:
            found = True
            if A[i] > A[i + 1]:
                to_delete = i + 1
            else:
                to_delete = i
            A.pop(to_delete)
            B.pop(to_delete)
            break
    if not found:
        break
print(len(A))
0

100% poprawności
50 % szybkości
w sumie 75%
dzięki
jakby kto miał coś szybszego to niech mu klawiatura lekką bęźdie ;)

0

Dwie wersje czytelna i mniej czytelna

def f(a, b):
    n = len(a)
    max_fish = 0
    r = 0
    
    for i in xrange(n):
        if b[i] == 0:
            if a[i] > max_fish:
                r += 1
        else:
            max_fish = max(max_fish, a[i])
    
    max_fish = 0
    for i in xrange(n - 1, -1, -1):
        if b[i] == 1:
            if a[i] > max_fish:
                r += 1
        else:
            max_fish = max(max_fish, a[i])

    return r

def process(x, y):
    if y[1] == 0:
        return (x[0] + (y[0] > x[1]), x[1])
    else:
        return (x[0], max(x[1], y[0]))
    
def f2(a, b):
    r = 0    
    
    r += reduce(process, zip(a, b), (0, 0))[0]
    r += reduce(process, zip(a, map(lambda x: x ^ 1, b))[::-1], (0, 0))[0]
    
    return r
0

co to reduce??
python nie rozumi

0
wohnioh napisał(a):

co to reduce??
python nie rozumi

W Pythonie 3 jest w module functools:
https://docs.python.org/3/library/functools.html#functools.reduce

1

rozwiązenie które napisałem po głębszym zamyśle i przeszło testy na 100%:

def solution(A,B):
    if len(A)>0:
        a = [A[0]]
        b = [B[0]]
        for i in range(1,len(A)):
            l2 = len(b)
            
            if (b[l2-1] == 0 and B[i] == 1 ) or b[l2-1] == B[i]:
                a.append(A[i])
                b.append(B[i])
            elif b[l2-1] == 1 and B[i] == 0:
                if a[l2-1] < A[i]:
                    a[l2-1] = A[i]
                    b[l2-1] = B[i]
                    if l2>1:
                        while a[len(a)-2] < a[len(a)-1] and (b[len(a)-2]==1 and b[len(a)-1] ==0):
                            l = len(a)
                            
                            a[l-2] = a[l-1]
                            b[l-2] = b[l-1]
                            a.pop(l-1)
                            b.pop(l-1)
                            if l == 1:
                                break
                        while a[len(a)-2] > a[len(a)-1] and (b[len(a)-2]==1 and b[len(a)-1] ==0):
                            l = len(a)
                            a.pop(l-1)
                            b.pop(l-1)
                            if l == 1:
                                break
       return len(b)

1 użytkowników online, w tym zalogowanych: 0, gości: 1