Hilf Beth, der Wüste zu entkommen

11

Die einzigartigen Aspekte dieser Herausforderung ähneln zwar dem anderen wasserführenden Puzzle , machen sie jedoch völlig anders.

Beth

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

  1. Beth lässt 1 vollen Eimer 3 km von der Oase entfernt und kehrt zurück (mit dem letzten Drink aus der Oase)
  2. Beth bringt am 3KM-Punkt einen weiteren vollen Eimer mit 12L.
  3. Beth kann bis zu 6 km vorrücken und einen Eimer mit 4 l Wasser darin lassen.
  4. Kommen Sie zurück zu 3 km Punkt. Sie hat jetzt genau 2L, um in die Oase zurückzukehren.
  5. Füllen Sie die Eimer und fahren Sie bis zum 6-km-Punkt. Sie hat jetzt 8L Wasser.
  6. 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.

romaninsh
quelle
2
Soll das Code Golf sein? Es ist als Code-Herausforderung markiert.
Dennis
Ja, es ist Code-Golf, ich habe das Tag hinzugefügt. Überlegen Sie sich eine korrekte Formel und drücken Sie sie durch den Code aus.
Romaninsh
1
Ich denke, es lohnt sich, Schritt 1 zu erweitern. Zunächst war mir nicht klar, wie Beth 6 km mit nur 5 Litern Wasser zurücklegen kann: Sie trinkt erst nach jedem Kilometer, den sie zurücklegt, und beim letzten ist sie in der Oase.
xnor
1
Könnten Sie einen Testfall so geben, wie ein Programm ihn ausgeben würde?
Pavel
Die Frage wurde bearbeitet, um beide Punkte anzusprechen.
Romaninsh

Antworten:

2

JavaScript (ES6), 25 Byte

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

Alle diese berechnen den gleichen Wert; Ich kann mir keine kürzere Formulierung einfallen lassen.

Wenn xweniger als 3, nehmen Sie so viel Wasser wie möglich und gehen so weit wie möglich, was einfach ist x*y+1.

Wenn xmindestens 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/2und 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/2einen vollen Eimer in einiger Entfernung stehen lassen yund zur Oase zurückkehren. Dazu benötigen Sie 3 Eimer.

Von der Oase aus, mit vollen Eimern an beiden yund y/2, können Sie einen vollen Eimer in einiger Entfernung stehen lassen 3y/2und zur Oase zurückkehren. Dazu benötigen Sie 4 Eimer. Sie müssen dann einen vollen Eimer in einiger Entfernung stehen lassen y/2und 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/2da Sie nicht in die Oase zurückkehren können, da die Hin- und Rückfahrt xydie Gesamtkapazität der Eimer darstellt.)

Mit Ihren restlichen Eimern können Sie volle Eimer bei (x-3)y/2... yoder lassen y/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/2Sie noch zwei volle Eimer übrig, so dass Sie erreichen können (x+3)y/2.

Das Extra 1kommt 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.

Neil
quelle