Todos os desafios
Difícil 1 resolvido 100.0% de aceitação

Corte um Retângulo em Quadrados

Encontre o menor número de cortes retos necessários para produzir apenas quadrados.

O que você vai aprender

  • Definir uma tabela DP por largura e altura
  • Testar cada corte horizontal e vertical
  • Reutilizar resultados de retângulos menores

Problema

Ver original (inglês)

A cada movimento, escolha um retângulo e corte-o completamente, paralelo a um dos lados, formando dois retângulos com lados de comprimento inteiro positivo. Continue até que cada pedaço seja um quadrado. Os quadrados podem ter tamanhos diferentes. Conte os cortes, não os pedaços.

Implemente rectangle_cutting(height, width).

Entrada

height: A altura do retângulo inicial.

width: A largura do retângulo inicial.

Saída

Retorne o número mínimo de cortes.

Restrições

1 ≤ height, width ≤ 500. Rotacionar não altera a resposta.

Exemplos

Exemplo 1
Entrada:
height = 2
width = 3

Saída esperada:
expected = 2
Entrada:
long long height = 2;
long long width = 3;

Saída esperada:
long long expected = 2;
Entrada:
long height = 2;
long width = 3;

Saída esperada:
long expected = 2;

Explicação

Corte um quadrado de 2 × 2, restando um retângulo de 2 × 1. Mais um corte divide o restante em dois quadrados unitários.

Exemplo 2
Entrada:
height = 4
width = 4

Saída esperada:
expected = 0
Entrada:
long long height = 4;
long long width = 4;

Saída esperada:
long long expected = 0;
Entrada:
long height = 4;
long width = 4;

Saída esperada:
long expected = 0;

Explicação

O retângulo inicial já é um quadrado.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Um retângulo pode ser resolvido dividindo-o em dois retângulos menores e combinando as melhores respostas.

Dica 2

Teste todas as divisões horizontais e verticais para encontrar o mínimo.

Dica 3

Memoização ou uma tabela ajuda porque muitos subretângulos se repetem.

Complexidade esperada

tempo O(h*w*(h+w)), espaço extra O(h*w)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 954 ms - 4/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 1 solução completa abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.