Question

Как известно, обычно штаны состоят из двух штанин. Однако собачке нужны, например, уже штаны из 5 штанин (для 4-х лап и хвоста), а сороконожке – штаны с 40 штанинами. У Пети живет Зверь, у которого M лап. Иногда – когда на улице особенно холодно, чтобы Зверь не простудился, на него бывает нужно надеть несколько штанов, чтобы на каждой лапе было надето по несколько штанин. Петина мама оставила Пете N штанов, имеющих соответственно K1, K2, …, KN штанин, наказав ему надеть на Зверя их все. Петя хочет надеть на Зверя штаны так, чтобы на самой «утепленной» лапе оказалось как можно меньше штанин, но при этом все оставленные мамой штаны были надеты на зверя. Любые штаны можно надевать на любой набор лап (каждая лапа встречается в наборе не более одного раза). Помогите ему – напишите программу, которая для каждых штанов укажет, на какие лапы должны быть надеты их штанины. Имейте в виду, что две штанины одних и тех же штанов не могут быть надеты на одну и ту же лапу (в то время как штанины разных штанов могут быть надеты на одну и ту же лапу). Входные данные Вводится сначала число M, а затем число N (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Выходные данные Выведите N строк, в i-ой строке должно быть выведено Ki различных чисел, обозначающих номера лап Зверя, на которые должны быть надеты штанины i-ых штанов. Лапы Зверя нумеруются натуральными числами от 1 до M. Если искомых ответов несколько, то выведите любой из них. Срочно прошу помочь

Answer 1

# # Код на ruby 2.2.3p173
def wearTrousersOnTheBeast(m, ks)
  leg = 0
  ks.each { |k|
    if not k.between?(1,m)
      puts "Неправильные штаны #{k}"
      next
    end

    legs = []
    for i in 1..k
      leg = (leg + 1 > m) ? 1 : leg + 1
      legs << leg
    end
    p legs
  }
end
# # # Примеры применения
wearTrousersOnTheBeast(4, [2,4,3,1,5])
wearTrousersOnTheBeast(10, [2,4,3,1,5])

Answer 2

Для решения этой задачи можно использовать жадный алгоритм. Идея заключается в том, чтобы для каждого штана найти лапу с минимальным числом уже надетых на нее штанин и надеть текущие штанины на эту лапу.

Вот пример кода на Python, который решает данную задачу:

pythonCopy code
def assign_pants_to_paws(M, N, pants):
    paws = [[] for _ in range(M)]  # Инициализируем список лап

    for i, num_pants in enumerate(pants, 1):
        for j in range(num_pants):
            min_paws = min(paws, key=len)  # Находим лапу с минимальным числом штанин
            min_paws.append(i)  # Надеваем штаны на эту лапу

    return paws

# Ввод данных
M = int(input("Введите количество лап у Зверя: "))
N = int(input("Введите количество штанов: "))
pants = list(map(int, input("Введите количество штанин для каждого штана через пробел: ").split()))

# Решение и вывод
result = assign_pants_to_paws(M, N, pants)
for paws in result:
    print(*paws)

Пример работы программы:

Copy code
Введите количество лап у Зверя: 4
Введите количество штанов: 3
Введите количество штанин для каждого штана через пробел: 2 3 1
1 2
3 4 1
2

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