Шоколадка

У Аленки есть шоколадка прямоугольной формы, размером n×m долек. Аленка разламывает ее на две части по вертикали или по горизонтали и съедает одну из двух частей. Если Аленка чувствует, что не наелась, то она снова может разломить оставшийся кусок на две части и съесть одну из них, и так далее. Всю шоколадку Аленка есть не будет, а оставит про запас как минимум одну дольку.

Производителям стало известно о такой привычке девочки и они захотели узнать, какое количество долек может быть съедено при таком алгоритме поедания шоколада. Они хотят, чтобы вы написали программу, которая по известному размеру шоколадки найдет все возможные количества съеденных долек и выведет их в порядке возрастания.

Рассмотрим такой пример. Шоколадка имеет размер 3×3. Тогда Аленка может разломить ее на две части 3×1 и 3×2. Таким образом, она сможет съесть 3 или 6 долек и остановиться. Но также Аленка сможет съесть кусок из 6 долек, а от оставшегося отломить 1 или 2 дольки и съесть еще и их. Таким образом, она сможет съесть 7 или 8 долек. Наконец, она сможет съесть кусок 3×1 а от оставшегося куска 3×2 отломить и съесть еще 2 дольки, тогда количество съеденных долек будет равно 5. Очевидно, что съесть 1, 2 или 4 дольки Аленка не сможет.

Формат входных данных
На вход в одной строке подается два натуральных числа n и m — размеры шоколадки. 1≤n,m≤100; n+m; 3n+m≥3.

Формат выходных данных
Программа должна вывести в одной строке через пробел все числа, являющиеся ответами к задаче. Числа должны выводиться в порядке возрастания без повторений.

Если вы программируете на Python, то убрать перенос строки в функции print можно при помощи именованного параметра end, например, print(a,end=' ').

Методика проверки
Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется.

Sample Input:
3 3

Sample Output:
3 5 6 7 8

Я написал код:Однако он работает только если n = m.
Пожалуйста, помогите решить задачу!

0

Решение на c++:Как перенести в python думайте сами!

0

Может быть, задача уже не актуальна, прошло уже больше двух лет.
Ваше решение не работает даже на квадратных плитках, показывает не все ответы.
Например, задавая плитку 10х10 в ответе нет 36, хотя легко можно отрезать сначала 20,
а затем 16 кусочков.
Сначала я решил её так:

n, m = map(int,input("Введи два числа n и m (размеры шоколадки):").split())
otvet = set()

for i in range(max(n,m)):
otvet.add(n * m - i - 1)

def rez(n_hor, n_ver, summa):
for num_rez in range(1, n_ver):
new_summa = summa + num_rez * n_hor
otvet.add(new_summa)
rez(n_hor, n_ver - num_rez, new_summa)
rez(n_ver - num_rez, n_hor, new_summa)

rez(n, m, 0)
if n != m:
rez(m,n, 0)

otvet_list = []
for s in otvet:
otvet_list.append(s)
otvet_list.sort()
s = ""
for i in otvet_list:
s += str(i) + " "
print(s)

Но, в результате она зависала на больших цифрах (очень много рекурсий)

В результате получилось вот что:

n, m = map(int,input("Введи два числа n и m (размеры шоколадки):").split())
otvet = set()
vars = set()

for i in range(max(n,m)):
otvet.add(n * m - i - 1)

def rez(n_hor, n_ver, summa):
#запоминаю все циклы, в которых копался
vars.add(str(summa) + " " + str(n_hor)+ " " + str(n_ver))
for num_rez in range(1, n_ver):
new_summa = summa + num_rez * n_hor
otvet.add(new_summa)
s = str(new_summa) + " " + str(n_hor) + " " + str(n_ver - num_rez)
#не вхожу в те циклы, в которых бывал
if s in vars:
return 0
rez(n_hor, n_ver - num_rez, new_summa)
s = str(new_summa) + " " + str(n_hor - num_rez) + " " + str(n_ver)
if s in vars:
return 0
rez(n_ver - num_rez, n_hor, new_summa)

rez(n, m, 0)
if n != m:
rez(m,n, 0)

otvet_list = []
for s in otvet:
otvet_list.append(s)
otvet_list.sort()
s = ""
for i in otvet_list:
s += str(i) + " "
print(s)

Добавлено через 4 часа 8 минут
Извините, это мой первый опыт, я только учусь

0