Zadanie 2.4. Osiągalność między punktami — informatyka 2022

Wprowadzenie

Dla danej, dodatniej liczby całkowitej N, na kartce papieru rysujemy N różnych punktów i numerujemy je liczbami 1, 2, …, N. W tym zadaniu będziemy łączyć punkty ze sobą strzałkami – funkcja strzałka(x,y) rysuje strzałkę od punktu o numerze x do punktu o numerze y.

Wywołanie poniżej zapisanej funkcji rekurencyjnej rysuj(x) poskutkuje narysowaniem pewnej liczby strzałek. Jej jedynym argumentem jest pewna liczba całkowita x z przedziału [1, N]. Przeanalizuj funkcję i znajdź odpowiedzi dla podanych zadań.

funkcja rysuj(x)
    jeżeli 2*x ≤ N
        strzałka(x, 2*x)
        rysuj(2*x)
    jeżeli 2*x + 1 ≤ N
        strzałka(x, 2*x + 1)
        rysuj(2*x + 1)

Przykład: Oto przykładowy rysunek otrzymany w wyniku wywołania rysuj(1) dla N = 5 i danego układu punktów:

Przykładowy układ pięciu punktów i strzałek funkcji rysuj(1).

Polecenie

W pliku pary.txt danych jest 1000 par liczb całkowitych z przedziału [1, 100 000], po jednej parze w wierszu. Liczby w każdym wierszu są rozdzielone znakiem odstępu. Druga liczba w parze zawsze jest większa od pierwszej.

Dla N = 100 000 wykonano polecenie rysuj(1) dla pewnego układu N punktów.

Napisz program, który znajdzie i wypisze te pary liczb z pliku pary.txt, które odpowiadają numerom punktów x i y takich, że z punktu o numerze x można przejść po jednej lub wielu strzałkach (zawsze zgodnie z ich zwrotami) do punktu o numerze y.

Przykład: Przykładowo: dla N = 5 po strzałkach można przejść z punktu o numerze 1 do punktu o numerze 4, ale nie można przejść z punktu o numerze 3 do punktu o numerze 5.

Do oceny oddajesz plik wyniki2.txt, zawierający odpowiedź do zadania 2.4., oraz plik(-i) zawierający(-e) kody źródłowe Twojego(-ich) programu(-ów). Brak tych plików jest równoznaczny z brakiem rozwiązania zadania.

Każdą parę zapisz jako x y, a kolejne pary oddziel średnikiem. Kolejność par jest dowolna.

Pary x y, oddzielone średnikami: …

Zasady oceniania CKE

3 pkt – odpowiedź poprawna.

2 pkt – za podanie co najmniej 5 poprawnych par.

1 pkt – za podanie co najmniej 1 poprawnej pary.

0 pkt – odpowiedź niepoprawna albo brak rozwiązania.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

47	3044
7650	61204
1	245
7	63669
9125	18250
5	43246

2.4. Osiągalność między punktami

Wprowadzenie

Polecenie

Odpowiedź CKE

Zasady oceniania CKE

Źródło

Przygotuj się do matury z informatyki ze mną.