Załóżmy, że otrzymałeś zestaw nie przecinających się przedziałów liczb całkowitych [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]
. (Gdzie [a,b]
jest liczbą całkowitą większą lub równą a
i mniejszą lub równą b
.)
Interwał w indeksie X
obejmuje bX - aX + 1
wartości. Zadzwonimy pod ten numer cX
.
Biorąc pod uwagę, że każdy interwał może być ...
- niezmieniony (pozostaje jako
[aX,bX]
), - przedłużony w prawo w stronę
+
boku numeru ocX
(staje się[aX,bX + cX]
), - lub przedłużony w lewo w stronę
-
boku numeru przezcX
(staje się[aX - cX,bX]
),
jaka jest maksymalna liczba wartości, które mogą być uwzględnione przez połączenie wszystkich zaktualizowanych przedziałów, biorąc pod uwagę, że wszystkie one nadal się nie przecinają?
Napisz funkcję lub program, który przyjmuje ciąg formularza [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]
i oblicza to maksimum. Jeśli piszesz funkcję, zwróć wartość. Jeśli piszesz pełny program, użyj stdin jako wejścia i wypisz wartość na stdout (lub użyj najbliższych alternatyw).
Możesz założyć, że wszystkie wartości mieszczą się w granicach normalnej 32-bitowej liczby całkowitej ze znakiem i że aX
jest mniejsza lub równa bX
dla wszystkich indeksów X
. Interwały mogą być w dowolnej kolejności, niekoniecznie zawsze się zwiększają. Muszą być podane jako ciąg znaków w powyższym formacie. Ciąg może być pusty, w takim przypadku odpowiedź będzie równa 0.
Najkrótsze przesłanie w bajtach wygrywa.
Przykład
Gdyby dane wejściowe były [-3,0],[1,2],[4,9]
wyjściowe, wyniósłby 22. Środkowy przedział nie ma miejsca na rozwinięcie w obu kierunkach, więc musi pozostać niezmieniony. Lewy i prawy interwał można wydłużyć odpowiednio do [-7,0]
i [4,15]
. Zjednoczenie [-7,0]
i [1,2]
i [4,15]
zawiera wszystkie wartości od -7 do 15, z wyjątkiem 3. To 22 wartości.
źródło
[5,6]
być[3,8]
(dla odpowiedzi 6), czy może być sprawiedliwy[5,8]
lub[3,6]
(dla odpowiedzi 4)?Odpowiedzi:
Haskell, 145 bajtów
Przykładowe przebiegi:
źródło
R,
282278269247To stało się bardzo szybko radzenie sobie z wprowadzaniem ciągu. Podejrzewam, że mogę lepiej grać w golfa, ale w tej chwili zabrakło mi czasu.
Zasadniczo chodzi o to
Edycja: zdałem sobie sprawę, że źle przeliczyłem znaki, a potem przegrupowałem kilka rzeczy, żeby trochę ogolić.
źródło