Die einzigartigen Aspekte dieser Herausforderung ähneln zwar dem anderen wasserführenden Puzzle , machen sie jedoch völlig anders.
Beth liegt in einer Oase mitten in der Wüste. Es gibt viel Wasser im See, aber leider gibt es nur X Eimer, von denen jeder ein Fassungsvermögen von Y Litern Wasser hat.
Beth kann 2 Eimer in den Händen halten, aber um zu überleben, muss sie nach jedem Kilometer genau 1 Liter trinken. Sie kann auch einige Eimer auf halbem Weg stehen lassen (Wasser verdunstet nicht).
Die Herausforderung
Finden Sie die Formel heraus und schreiben Sie die kürzeste Lösung , die für positive ganzzahlige Werte von X und Y funktioniert, und berechnen Sie die maximale Entfernung, die Beth von der Oase zurücklegen kann. Das Bewegen von Wasser zwischen den Eimern ist zulässig.
Beispiel
X = 3, Y = 5
- Beth lässt 1 vollen Eimer 3 km von der Oase entfernt und kehrt zurück (mit dem letzten Drink aus der Oase)
- Beth bringt am 3KM-Punkt einen weiteren vollen Eimer mit 12L.
- Beth kann bis zu 6 km vorrücken und einen Eimer mit 4 l Wasser darin lassen.
- Kommen Sie zurück zu 3 km Punkt. Sie hat jetzt genau 2L, um in die Oase zurückzukehren.
- Füllen Sie die Eimer und fahren Sie bis zum 6-km-Punkt. Sie hat jetzt 8L Wasser.
- Fahren Sie bis zum 15-km-Punkt fort.
Die Antwort lautet: 15
Input-Output
Sie können X / Y direkt im Code definieren oder aus der Eingabe lesen. Das Ergebnis kann in einer Variablen oder Ausgabe platziert werden, je nachdem, was am kürzesten ist.
quelle
Antworten:
JavaScript (ES6), 25 Byte
Alle diese berechnen den gleichen Wert; Ich kann mir keine kürzere Formulierung einfallen lassen.
Wenn
x
weniger als3
, nehmen Sie so viel Wasser wie möglich und gehen so weit wie möglich, was einfach istx*y+1
.Wenn
x
mindestens 3 ist, müssen Sie mit dem Erstellen von Caches beginnen.Von der Oase aus können Sie einen vollen Eimer in einiger Entfernung stehen lassen
y/2
und zur Oase zurückkehren. Sie benötigen 2 Eimer, um dies zu tun, aber dies ist nicht nützlich, wenn Sie nur 2 Eimer haben, da Sie in der Lage sein möchten, 2 Eimer zu füllen, wenn Sie in die Oase zurückkehren.Von der Oase aus können Sie mit einem Eimer in einiger Entfernung
y/2
einen vollen Eimer in einiger Entfernung stehen lasseny
und zur Oase zurückkehren. Dazu benötigen Sie 3 Eimer.Von der Oase aus, mit vollen Eimern an beiden
y
undy/2
, können Sie einen vollen Eimer in einiger Entfernung stehen lassen3y/2
und zur Oase zurückkehren. Dazu benötigen Sie 4 Eimer. Sie müssen dann einen vollen Eimer in einiger Entfernung stehen lasseny/2
und zur Oase zurückkehren.Schließlich können Sie mit einem vollen Eimer bei enden
(x-1)y/2
. (Sie können keinen vollen Eimer bei lassen,xy/2
da Sie nicht in die Oase zurückkehren können, da die Hin- und Rückfahrtxy
die Gesamtkapazität der Eimer darstellt.)Mit Ihren restlichen Eimern können Sie volle Eimer bei
(x-3)y/2
...y
oder lasseny/2
. An diesem Punkt gehen Sie einfach so weit wie möglich und nehmen dabei Ihre vollen Eimer auf. Wenn Sie erreichen, haben(x-1)y/2
Sie noch zwei volle Eimer übrig, so dass Sie erreichen können(x+3)y/2
.Das Extra
1
kommt von der Eigenart in den Regeln, die es Ihnen ermöglichen, Ihre letzte Meile ohne Wasser zu laufen. Obwohl das Beispiel zeigt, dass Sie die Eimer etwas weiter entfernt als oben beschrieben lassen können, hilft Ihnen dies nicht weiter, da Sie entweder weniger Wasser lassen oder das Wasser aus dem Eimer trinken müssen, wenn Sie ihn erreichen, bevor Sie sich bewegen können auf.quelle