Basen

Zadanie o nazwie Basen pochodzi z Olimpiady Informatycznej Juniorów (OIJ) rozgrywanej w roku 2019/2020. Olimpiada jest przeznaczona dla uczniów klas szkoły podstawowej, a więcej o niej można się dowiedzieć z jej strony: oij.edu.pl. Na tej stronie publikuję przykładowe rozwiązanie, które wygeneruje nam 100 punkowy wynik.

Treść zadania

Bajtek w końcu kupił sobie wodoodporny smartwatch. Od razu poszedł na basen, by sprawdzić czy działa. Okazało się, że zegarek jest dość dziwny. W różnych momentach zapisywał on jak daleko Bajtek był od początku basenu, tj. od brzegu, z którego wystartował. Bajtek odczytał ciąg kolejnych zarejestrowanych odległości z zegarka, nie bardzo rozumie jednak, jak zinterpretować ten wynik. Chciałby się dowiedzieć, ile minimalnie długości basenu przepłynął. Możesz założyć, że Bajtek zawracał jedynie po dopłynięciu do końca basenu oraz zaczynał od brzegu i kończył przy brzegu (choć nie musiał tego zarejestrować zegarek). Bajtek mógł się także czasami zatrzymywać dla odpoczynku, niekoniecznie przy brzegu basenu.

Napisz program, który: wczyta odczyty zegarka Bajtka, wyznaczy minimalną możliwą liczbę długości basenu, jakie przepłynął Bajtek i wypisze wynik na standardowe wyjście

Przykładowe wejścia i wyjścia

  • Dla liczby pomiarów 7 i odczytów 3, 7, 11, 6, 2, 4 wyjściem powinno być 3,
  • Dla liczby pomiarów 9 i odczytów 1,2,3,4,5,4,3,2,1 wyjściem powinno być 2,
  • Dla liczby pomiarów 5 i odczytów 28,28,28,28,28 wyjściem powinno być 1

Pełna treść zadania znajduje się tutaj.

Kod programu

odczyty = 1000000
pomiar = [998000002+i for i in range(1,odczyty+1)]

pomiar.insert(0,0)

res = [0]

for i in range(1, odczyty + 1):
    if pomiar[i] - pomiar[i-1] > 0 and res[-1] != 1:
        res.append(1)
    elif pomiar[i] - pomiar[i-1] < 0 and res[-1] != -1:
        res.append(-1)

print(len(res)-1)

Skrypt używa tylko jednej pętli do sprawdzenia ile długości zostało przepłyniętych. Opiera się o sprawdzanie różnic między poszczególnymi odczytam i zaznaczaniu, kiedy Bajtek oddala się od pola startowego, a kiedy rozpoczyna powrót w jego kierunku.