Pomóż Beth uciec z pustyni

Choć podobne do innych puzzli niosących wodę , wyjątkowe aspekty tego wyzwania sprawiają, że jest zupełnie inny.

Beth znajduje się w oazie na środku pustyni. W jeziorze jest dużo wody, ale niestety są tylko X wiader, z których każdy ma pojemność Y litrów wody.

Beth może nosić w rękach 2 wiadra, ale aby przeżyć, musi wypić dokładnie 1 litr po każdym przejechanym kilometrze. Może też zostawić trochę wiader do połowy (woda nie odparowuje).

Wyzwanie

Wymyśl wzór i napisz najkrótsze rozwiązanie, które będzie działać dla dodatnich liczb całkowitych X i Y, i obliczyć maksymalną odległość Beth może pokonać z oazy. Dozwolone jest przenoszenie wody między wiadrami.

Przykład

X = 3, Y = 5

Beth pozostawia 1 pełne wiadro 3 km od oazy, wraca (po ostatnim drinku z oazy)
Beth przynosi kolejne pełne wiadro w punkcie 3 km, mając teraz 12 l.
Beth może przejść do punktu 6 km i zostawić wiadro z 4 litrami wody.
Wróć do punktu 3 km. Ma teraz dokładnie 2 litry, aby wrócić do oazy.
Wypełnij wiadra i przejdź do punktu 6 km. Ma teraz 8 litrów wody.
Kontynuuj aż do punktu 15 km.

Odpowiedź brzmi: 15

Wejście wyjście

Możesz zdefiniować X / Y bezpośrednio w kodzie lub odczytać z wejścia. Wynik można umieścić w zmiennej lub wyniku, w zależności od tego, który jest najkrótszy.

code-golf math puzzle-solver romaninsh
źródło

Czy to ma być golf golfowy? Jest oznaczony jako wyzwanie kodowe.

Dennis

Tak, to kod-golf, dodałem tag. Wymyśl prawidłową formułę i wyraż ją poprzez kod.

romaninsh

Myślę, że warto rozwinąć w kroku 1. Na początku nie było dla mnie jasne, jak Beth może pokonać 6 km przy zaledwie 5 litrach wody: pije tylko po każdym przejechanym kilometrze, a na końcu jest w oazie.

xnor

Czy możesz podać przypadek testowy w sposób, w jaki program go wypisze?

Pavel

Edytowałem pytanie, aby uwzględnić oba punkty.

romaninsh

Odpowiedzi:

JavaScript (ES6), 25 bajtów

x=>y=>((x<3?x:3)+x)*y/2+1
x=>y=>(x<3?x+x:x+3)*y/2+1
x=>y=>(x<3?x:(x+3)/2)*y+1
x=>y=>(x<3?x:x/2+1.5)*y+1

Wszystkie obliczają tę samą wartość; Nie wydaje mi się, aby wymyślić krótsze sformułowanie.

Kiedy xjest mniej niż 3, bierz tyle wody, ile możesz i idź tak daleko, jak to możliwe, co jest po prostu x*y+1.

Kiedy xjest co najmniej 3, musisz zacząć budować skrzynki.

Z oazy możesz zostawić pełne wiadro na odległość y/2i wrócić do oazy. Aby to zrobić, potrzebujesz 2 wiader, ale nie jest to przydatne, jeśli masz tylko 2 wiadra, ponieważ chcesz móc napełnić 2 wiadra po powrocie do oazy.

Z oazy, z wiadrem na odległość y/2, możesz zostawić pełne wiadro na odległość yi wrócić do oazy. Aby to zrobić, potrzebujesz 3 wiader.

Z oazy, z pełnymi wiadrami na obu yi y/2można zostawić pełne wiadro na odległość 3y/2i powrót do oazy. Aby to zrobić, potrzebujesz 4 wiader. Następnie musisz zostawić pełne wiadro w odległościy/2 i wrócić do oazy.

W końcu możesz skończyć z pełnym wiadrem na (x-1)y/2. (Nie możesz zostawić pełnego wiadra na, xy/2ponieważ nie byłbyś w stanie wrócić do oazy, ponieważ w obie strony jest xycałkowita pojemność wiader.)

Korzystając z pozostałych wiader, możesz zostawić pełne wiadra w (x-3)y/2... ylub y/2. W tym momencie po prostu idź tak daleko, jak to możliwe, zbierając pełne wiadra podczas podróży. Po dotarciu (x-1)y/2pozostały ci jeszcze dwa pełne wiadra, dzięki czemu możesz dosięgnąć(x+3)y/2 .

Dodatek 1pochodzi z dziwactwa w przepisach, które pozwalają przejść ostatnią milę bez wody. Chociaż przykład pokazuje, że możesz zostawić wiadra nieco dalej niż opisano powyżej, to tak naprawdę nie pomaga ci iść dalej, ponieważ albo musisz zostawić mniej wody, albo napić się wody z wiadra, zanim do niego dojdziesz. na.

Neil
źródło