Подобные другой водной головоломке , уникальные аспекты этой задачи делают ее совершенно другой.
Бет находится в оазисе посреди пустыни. В озере много воды, но, к сожалению, есть только X ведер, каждое из которых рассчитано на Y литров воды.
Бет может нести 2 ведра в руках, но чтобы выжить, она должна выпивать ровно 1 литр после каждого пройденного километра. Она также может оставить несколько ведер на полпути (вода не испаряется).
Соревнование
Выясните формулу и напишите кратчайшее решение, которое будет работать для положительных целых значений X и Y, и рассчитайте максимальное расстояние, которое Бет может пройти от оазиса. Перемещение воды между ведрами разрешено.
пример
X = 3, Y = 5
- Бет оставляет 1 полное ведро на расстоянии 3 км от оазиса и возвращается обратно (выпив последний напиток из оазиса)
- Бет приносит еще одно полное ведро в точке 3 км, имея там 12 л.
- Бет может продвинуться до точки 6 км и оставить ведро с 4 л воды в нем.
- Вернитесь к точке 3 км. Теперь у нее ровно 2 литра, чтобы вернуться в оазис.
- Заполните ведра и отправляйтесь в пункт 6 км. Сейчас у нее 8 л воды.
- Продолжить весь путь до 15 км.
Ответ: 15
Ввод, вывод
Вы можете определить X / Y непосредственно в коде или прочитать из ввода. Результат может быть помещен в переменную или в выходной, в зависимости от того, что является самым коротким.
источник
Ответы:
JavaScript (ES6), 25 байт
Все они вычисляют одно и то же значение; Я не могу придумать более короткую формулировку.
Когда
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
прибывает из причуд в правилах, позволяющих Вам пройти свою последнюю милю без воды. Хотя пример показывает, что вы можете оставить ведра немного дальше, чем описано выше, на самом деле это не поможет вам идти дальше, так как вам придется либо оставлять меньше воды, либо пить воду из ведра, когда вы достигнете его, прежде чем сможете двигаться на.источник