Как разбить числа от 1 до n на три множества так, чтобы сумма чисел в каждом была одинаковой?
Вам дано число n. Разбейте все натуральные числа от 1 до n на три множества так, чтобы сумма чисел в каждом множестве была одинаковой. Не понимаю с какой стороны зайти
Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5
2
1 4
2
2 3
1
5
Это мой код:
n = int(input())
def divide_numbers(n):
if n * (n + 1) / 2 % 3 == 0:
numbers = [i for i in range(1, n+1)]
total_sum = sum(numbers)
set_sum = total_sum // 3
sets = [[], [], []]
for num in numbers:
if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
sets[0].append(num)
elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
sets[1].append(num)
else:
sets[2].append(num)
return sets
else:
return -1
a = divide_numbers(n)
if a != -1:
first = a[0]
len_first = len(first)
second = a[1]
len_second = len(second)
thired = a[2]
len_thired = len(thired)
print(len_first)
print(*first)
print(" ")
print(len_second)
print(*second)
print(" ")
print(len_thired)
print(*thired)
else: print(a)
Для примера в своем коде я взял n = 5, ниже - вывод:
2
1 2
1
3
2
4 5
Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.
Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5
2
1 4
2
2 3
1
5
Это мой код:
n = int(input())
def divide_numbers(n):
if n * (n + 1) / 2 % 3 == 0:
numbers = [i for i in range(1, n+1)]
total_sum = sum(numbers)
set_sum = total_sum // 3
sets = [[], [], []]
for num in numbers:
if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
sets[0].append(num)
elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
sets[1].append(num)
else:
sets[2].append(num)
return sets
else:
return -1
a = divide_numbers(n)
if a != -1:
first = a[0]
len_first = len(first)
second = a[1]
len_second = len(second)
thired = a[2]
len_thired = len(thired)
print(len_first)
print(*first)
print(" ")
print(len_second)
print(*second)
print(" ")
print(len_thired)
print(*thired)
else: print(a)
Для примера в своем коде я взял n = 5, ниже - вывод:
2
1 2
1
3
2
4 5
Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.