Schneide ein Rechteck in Quadrate

Wähle bei jedem Zug ein Rechteck aus und schneide es vollständig, parallel zu einer Seite, sodass zwei Rechtecke mit positiven ganzzahligen Seitenlängen entstehen. Fahre fort, bis jedes Teilstück ein Quadrat ist. Die Quadrate dürfen unterschiedlich groß sein. Zähle die Schnitte, nicht die Stücke.

Implementiere rectangle_cutting(height, width).

Eingabe

height: Die Höhe des Startrechtecks.

width: Die Breite des Startrechtecks.

Ausgabe

Gib die minimale Anzahl der benötigten Schnitte zurück.

Einschränkungen

1 ≤ height, width ≤ 500. Eine Drehung verändert die Antwort nicht.

Beispiele

Eingabe:
width = 3
height = 2

Erwartete Ausgabe:
expected = 2

Eingabe:
long long width = 3;
long long height = 2;

Erwartete Ausgabe:
long long expected = 2;

Eingabe:
long width = 3;
long height = 2;

Erwartete Ausgabe:
long expected = 2;

Eingabe:
width = 4
height = 4

Erwartete Ausgabe:
expected = 0

Eingabe:
long long width = 4;
long long height = 4;

Erwartete Ausgabe:
long long expected = 0;

Eingabe:
long width = 4;
long height = 4;

Erwartete Ausgabe:
long expected = 0;

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

• Rectangle Cutting — 1744