Помогите Бет сбежать из пустыни

11

Подобные другой водной головоломке , уникальные аспекты этой задачи делают ее совершенно другой.

в промежутке

Бет находится в оазисе посреди пустыни. В озере много воды, но, к сожалению, есть только X ведер, каждое из которых рассчитано на Y литров воды.

Бет может нести 2 ведра в руках, но чтобы выжить, она должна выпивать ровно 1 литр после каждого пройденного километра. Она также может оставить несколько ведер на полпути (вода не испаряется).

Соревнование

Выясните формулу и напишите кратчайшее решение, которое будет работать для положительных целых значений X и Y, и рассчитайте максимальное расстояние, которое Бет может пройти от оазиса. Перемещение воды между ведрами разрешено.

пример

X = 3, Y = 5

  1. Бет оставляет 1 полное ведро на расстоянии 3 км от оазиса и возвращается обратно (выпив последний напиток из оазиса)
  2. Бет приносит еще одно полное ведро в точке 3 км, имея там 12 л.
  3. Бет может продвинуться до точки 6 км и оставить ведро с 4 л воды в нем.
  4. Вернитесь к точке 3 км. Теперь у нее ровно 2 литра, чтобы вернуться в оазис.
  5. Заполните ведра и отправляйтесь в пункт 6 км. Сейчас у нее 8 л воды.
  6. Продолжить весь путь до 15 км.

Ответ: 15

Ввод, вывод

Вы можете определить X / Y непосредственно в коде или прочитать из ввода. Результат может быть помещен в переменную или в выходной, в зависимости от того, что является самым коротким.

romaninsh
источник
2
Это должен быть код гольф? Это помечено как вызов кода.
Деннис
Да, это код-гольф, я добавил тег. Придумайте правильную формулу и выразите ее через код.
Романиньш
1
Я думаю, что стоит остановиться на шаге 1. Сначала мне было непонятно, как Бет может проехать 6 км, имея всего 5 литров воды: она пьет только после каждого пройденного километра, а в последний - в оазисе.
xnor
1
Не могли бы вы дать контрольный пример, как программа выводит его?
Павел
Отредактировал вопрос, чтобы решить оба вопроса.
Романиньш

Ответы:

2

JavaScript (ES6), 25 байт

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

Все они вычисляют одно и то же значение; Я не могу придумать более короткую формулировку.

Когда xменьше 3, вы берете столько воды, сколько можете и идете так далеко, как можете, что просто x*y+1.

Когда xне менее 3, вы должны начать строить кеши.

Из оазиса вы можете оставить полное ведро на расстоянии y/2и вернуться в оазис. Для этого вам нужно 2 корзины, но это бесполезно, если у вас есть только 2 корзины, потому что вы хотите иметь возможность заполнить 2 корзины, когда вы вернетесь в оазис.

Из оазиса, с ведром на расстоянии y/2, вы можете оставить полное ведро на расстоянии yи вернуться в оазис. Вам нужно 3 ведра, чтобы сделать это.

Из оазиса, с полными ведрами на обоих yи y/2, вы можете оставить полное ведро на расстояние 3y/2и возвращении к оазису. Вам нужно 4 ведра, чтобы сделать это. Затем вы должны оставить полное ведро на расстоянии y/2и вернуться в оазис.

В конце концов вы можете закончить с полным ведром в (x-1)y/2. (Вы не можете оставить полное ведро в, xy/2потому что вы не сможете вернуться в оазис, так как в оба конца xy, общая вместимость ведер.)

Используя оставшиеся корзины, вы можете оставить полные корзины в (x-3)y/2... yили y/2. В этот момент вы просто идете так далеко, как можете, собирая свои полные ведра на ходу. Когда вы достигнете, у (x-1)y/2вас останется два полных ведра, что позволит вам достичь (x+3)y/2.

Дополнительное 1прибывает из причуд в правилах, позволяющих Вам пройти свою последнюю милю без воды. Хотя пример показывает, что вы можете оставить ведра немного дальше, чем описано выше, на самом деле это не поможет вам идти дальше, так как вам придется либо оставлять меньше воды, либо пить воду из ведра, когда вы достигнете его, прежде чем сможете двигаться на.

Нил
источник