Zadanie 3. Ulubione liczby

Małgosia i Jaś lubią liczby. Małgosia lubi liczby nieparzyste, a Jaś lubi liczby parzyste. Każde z dzieci zapisało po kilka spośród swoich ulubionych liczb na jednej wspólnej kartce. Najpierw Małgosia zapisała wszystkie swoje liczby, a potem Jaś dopisał swoje.

Napisz algorytm (w postaci listy kroków, za pomocą pseudokodu lub w wybranym języku programowania), który dla danego ciągu liczb zapisanych przez dzieci znajdzie pierwszą liczbę zapisaną przez Jasia. Zakładamy, że każde z dzieci zapisało co najmniej jedną liczbę.

Przy ocenie będzie brana pod uwagę złożoność czasowa twojego algorytmu. Maksymalną liczbę punktów uzyskasz za algorytm o złożoności lepszej niż liniowa.

Specyfikacja problemu:

Dane:

• n – liczba całkowita większa od 1

• A[1..n] – tablica zawierająca ciąg n liczb zapisanych przez dzieci (najpierw wszystkie liczby nieparzyste, a potem wszystkie liczby parzyste)

Wynik:

• w – pierwsza od lewej parzysta liczba w tablicy A

Przykład:

Dane:

• n = 10

• A[1..n] = {5, 99, 3, 7, 111, 13, 4, 24, 4, 8}

Wynik:

• w = 4

Schemat oceniania

• 5 pkt – za poprawny algorytm o złożoności czasowej mniejszej niż liniowa, w tym:

  • 1 pkt – za prawidłowy warunek pętli,

  • 1 pkt – za prawidłowe wyznaczenie podziału ciągu liczb,

  • 1 pkt – za prawidłowe wyznaczenie początku podciągu liczb,

  • 1 pkt – za prawidłowe wyznaczenie końca podciągu liczb,

  • 1 pkt – za prawidłowe wyznaczenie pierwszego elementu parzystego w A[1..n] (lub jego indeksu),

• 3 pkt – za poprawny algorytm o złożoności czasowej liniowej, w tym:

  • 1 pkt – za prawidłowy przebieg pętli,

  • 1 pkt – za sprawdzenie warunku (parzystości liczby),

  • 1 pkt – za prawidłowe wyznaczenie pierwszego elementu parzystego w A[1..n] (lub jego indeksu),

• 0 pkt – za błędną odpowiedź albo brak odpowiedzi.