Minimale Schritte von Quelle zu Ziel

Question

Wir haben einen Pfad auf der X-Achse von 1 bis N. Es gibt 2 Punkte nämlich Quelle, S und Ziel, D auf dem Pfad. Ausgehend von der Quelle S dürfen wir nur 2 Züge machen. Wir können entweder U Schritte vorwärts springen oder L Schritte rückwärts springen. Wenn wir uns an einer Position p befinden, können wir entweder in einem einzigen Schritt zu p + U oder p-L gehen, vorausgesetzt, sie bleiben im [1, N] -Bereich. Wie viele Schritte sind erforderlich, um das Ziel D von S aus zu erreichen? Wir sind nicht über die Grenzen erlaubt 1 und N zu erreichen

Answer 1

wir D Also müssen machen - S Schritte und wollen die minimale x+y:

D - S = x * U - y * L 

y = (Ux + S-D)/L 

Das ist Mathematik. So können wir Symmetrie im Problem ausnutzen und D> S (falls gewünscht), U> 0, L> 0 annehmen.

Um genau D zu treffen, muss Ux+S-D % L 0 sein (% ist der Modulooperator).

Entweder clevere Mathematik oder Schleife über x.

Ich hoffe, dass Sie damit beginnen.

---

Da mir bewusst ist, dass je nach Mathe behandelt die Klugheit variieren kann. Wenn sie gcd und Modulo behandelt:

Let g = gcd(U, L) 

dann gibt es keine Lösung, wenn (D-S) % g != 0. Zum Beispiel können Sie nicht für 3 bis 6 mit L 2 und U 4 erreichen.