Maksymalnie wydłuż interwały całkowite

14

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.

Hobby Calvina
źródło
3
Czy możemy użyć natywnej reprezentacji ciągów tablic naszego języka do wprowadzania danych, czy też musi to być dokładnie ten format?
Martin Ender
@ MartinBüttner Nie. Musisz użyć dokładnie tego formatu. (Wiem, że to rodzaj obosiecznego miecza, ale tak to działa.)
Hobby Calvina
Czy możesz wydłużyć dany interwał po obu stronach? Na przykład może [5,6]być [3,8](dla odpowiedzi 6), czy może być sprawiedliwy [5,8]lub [3,6](dla odpowiedzi 4)?
MtnViewMark
@MtnViewMark Nie. Można je rozszerzyć tylko z jednej strony (lub wcale)
Calvin's Hobbies

Odpowiedzi:

4

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
MtnViewMark
źródło
1

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

MickyT
źródło