2.4 Pary połączone strzałkami w pliku przykładowym

Matura próbna grudzień 2022 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 2.4 (3 pkt): plik `pary.txt` ma 1000 par liczb \( x < y \) z zakresu [1, 100 000], a strzałki narysowano dla \( N = 100\,000 \). Które pary to punkty, między którymi da się przejść po strzałkach z \( x \) do \( y \)? Zamiast rysować 99 999 strzałek, od \( y \) idzie się wstecz (dzielenie przez 2), aż liczba spadnie do \( x \) albo poniżej. Arkusz nie daje pliku przykładowego: `pary_przyklad.txt` to pierwsze 300 par z `pary.txt`. Jest w nich jedna taka para: 47 3044.

pairs = []
with open("pary_przyklad.txt") as f:
    for line in f:
        x, y = line.split()
        pairs.append((int(x), int(y)))

# z punktu k wychodzą strzałki do 2k i 2k + 1, więc do punktu y prowadzi jedna strzałka:
# z y // 2; idąc od y wstecz dzieleniem przez 2 trafia się po kolei we wszystkie punkty,
# z których da się dojść do y
def reachable(x, y):
    while y > x:
        y = y // 2
    return y == x


connected = [(x, y) for x, y in pairs if reachable(x, y)]

for x, y in connected:
    print(x, y)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.