Я уверен, что кто-то сможет реорганизовать и очистить этот код, но проблема заинтересовала меня достаточно, чтобы попытаться решить ее, прежде чем я отправлюсь на пробежку. Я с нетерпением жду некоторых комментариев о том, как его очистить, но на основе 3 приведенных примеров и ожидаемых ответов этот код, похоже, работает.
Идея в том, что вы превращаете маленькие плитки в максимально возможное количество больших плиток. Затем вы определяете, какой самый большой квадрат вы можете сделать из общих больших плиток (больших и преобразованных маленьких). Как только вы узнаете это, вы определите, сколько из общих больших плиток вы не использовали, и, по возможности, преобразуйте их обратно в маленькие плитки.
Ключевым моментом здесь является то, что если у вас больше запасных больших плиток, чем у маленьких, вы возвращаете все маленькие плитки, поскольку они вам не нужны. Если у вас меньше запасных плиток, чем у маленьких, то вы возвращаете все запасные части, которые вы не использовали в качестве маленьких плиток.
Теперь мы разработали самый большой квадрат, который мы можем сделать из n, мы будем использовать оставшиеся m, чтобы расширить квадрат. Таким образом, чтобы вычислить, сколько м нам нужно, мы вычислим самую длинную длину квадрата, умножим ее на 2 и добавим 1 для угловой части.
теперь мы просто l oop, в то время как у нас больше m, чем нам нужно, чтобы расширить квадрат. каждый раз, когда мы вычитаем эти m из доступных m, увеличиваем самую длинную длину и вычисляем, сколько нам нужно продлить снова.
ОБНОВЛЕНИЕ - Код с измененным рефакторингом, чтобы сделать его более читабельным
import math
from typing import Tuple
def largest_square_num(number: int) -> int:
while number > 1:
sqrt = math.sqrt(number)
if sqrt == int(sqrt):
break
else:
number -= 1
return number
def convert_m_to_n(m: int) -> Tuple[int, int]:
n_from_m = m // 4
m_after_n = m % 4
return n_from_m, m_after_n
def convert_n_to_m_limit(n: int, limit: int) -> int:
if n > limit:
m = limit * 4
else:
m = n * 4
return m
def calulate_largest_side_of_square(m, n):
# build as many n's from m's and store the new n's and remaining m's
n_from_m, m_after_n = convert_m_to_n(m)
total_n = n + n_from_m
# calculate the largest square that can be made from total n's
largest_square_of_n = largest_square_num(total_n)
longest_length = math.sqrt(largest_square_of_n) * 2
# restore m's back from spare n's but not more than we took from m's
restored_m = convert_n_to_m_limit(total_n - largest_square_of_n, n_from_m)
total_m = restored_m + m_after_n
# now we have the biggest n square extent it while we have enough m's
while True:
m_needed_to_extend = longest_length * 2 + 1
if total_m < m_needed_to_extend:
break
total_m -= m_needed_to_extend
longest_length += 1
return int(longest_length)
tests = [(4, 3), (13, 3), (1, 2), (9, 1), (0, 0), (5, 1)]
for n, m in tests:
print(f"{m=}, {n=}, longest_side={calulate_largest_side_of_square(n, m)}")
ВЫХОД
m=3, n=4, longest_side=4
m=3, n=13, longest_side=5
m=2, n=1, longest_side=2
m=1, n=9, longest_side=3
m=0, n=0, longest_side=0
m=5, n=1, longest_side=3