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ą ai mniejszą lub równą b.)

Interwał w indeksie Xobejmuje bX - aX + 1wartoś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 o cX(staje się [aX,bX + cX]),
• lub przedłużony w lewo w stronę -boku numeru przez cX(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 aXjest mniejsza lub równa bXdla 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.

Haskell, 145 bajtów

import Data.List
x=maximum.map length.filter(nub>>=(==)).map concat.sequence.map(\[a,b]->[[2*a-b-1..b],[a..b],[a..2*b-a+1]]).read.('[':).(++"]")

Przykładowe przebiegi:

λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22

R, 282 278 269 247

To 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.

f=function(s){i=matrix(strtoi(strsplit(gsub('[^0-9,-]','',s),',')[[1]]),nrow=2);l=0;if((a<-length(b<-order(i[1,])))>0){if(a>1)i=i[,b];l=diff(i[,1:a])+1;x=c(t(i));for(n in 1:a)if(n==1|n==a|x[n]-l[n]>x[n+a-1]|x[n+a]+l[n]<x[n+1])l[n]=l[n]*2;};sum(l)}

Zasadniczo chodzi o to

• Weź ciąg i zamień go w macierz 2-rzędową
• Upewnij się, że jest w odpowiedniej kolejności
• Opracuj różnice dla każdej kolumny
• Podwój pierwszą i ostatnią różnicę
• Podwój średnią różnicę, jeśli mają wystarczająco dużą lukę w stosunku do poprzedniego lub następnego
• Zwróć sumę różnic

Edycja: zdałem sobie sprawę, że źle przeliczyłem znaki, a potem przegrupowałem kilka rzeczy, żeby trochę ogolić.