Découper un rectangle en carrés

À chaque étape, choisissez un rectangle et coupez-le entièrement, parallèlement à l'un de ses côtés, de façon à obtenir deux rectangles dont les côtés sont des entiers strictement positifs. Continuez jusqu'à ce que chaque morceau soit un carré. Les carrés peuvent être de tailles différentes. Comptez le nombre de découpes, pas le nombre de morceaux.

Implémentez rectangle_cutting(height, width).

Entrée

height : La hauteur du rectangle de départ.

width : La largeur du rectangle de départ.

Sortie

Retournez le nombre minimal de découpes.

Contraintes

1 ≤ height, width ≤ 500. La rotation ne change pas la réponse.

Exemples

Entrée :
width = 3
height = 2

Sortie attendue :
expected = 2

Entrée :
long long width = 3;
long long height = 2;

Sortie attendue :
long long expected = 2;

Entrée :
long width = 3;
long height = 2;

Sortie attendue :
long expected = 2;

Entrée :
width = 4
height = 4

Sortie attendue :
expected = 0

Entrée :
long long width = 4;
long long height = 4;

Sortie attendue :
long long expected = 0;

Entrée :
long width = 4;
long height = 4;

Sortie attendue :
long expected = 0;

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

• Rectangle Cutting — 1744