Question

ДАЮ 100 БАЛЛОВ!!!ПРОШУ, РЕШИТЕ, ИЛИ ХОТЯ БЫ НАМЕКНИТЕ!n человек разбили на m команд так, что в каждой команде есть хотя бы один человек. Все члены каждой команды обменялись рукопожатиями. Посчитайте минимальное и максимальное число возможных рукопожатий. Программа получает на вход целые числа n и m, 1≤m≤n≤100, каждое в отдельной строке, и должна вывести два числа — минимальное и максимальное число рукопожатий.

Answer 1

Ответ:

Объяснение:

Введу две новые переменные: div(n, m) = a и mod(n, m) = b, где div и mod - целая часть и остаток от деления n на m.

Если в команде k человек, у них будет k (k - 1)/2 рукопожатий: каждый из k людей пожмет руку (k - 1) человеку, но каждое рукопожатие будет посчитано дважды.

Сначала порассуждаем о минимальном количестве рукопожатий. Пусть в одной группе a человек, в другой b, и a - b > 1. Тогда всего рукопожатий в этих двух группах

$\dfrac{a(a-1)}2+\dfrac{b(b-1)}2$

Переведём одного человека из большой группы в малую. Новое число рукопожатий

$\dfrac{(a-1)(a-2)}2+\dfrac{b(b+1)}2$

Считаем, на сколько изменилось общее число рукопожатий:

$\left(\dfrac{(a-1)(a-2)}2+\dfrac{b(b+1)}2\right)-\left(\dfrac{a(a-1)}2+\dfrac{b(b-1)}2\right)=\\=1-(a-b)$

Поскольку мы считали, что a - b > 1, то после перевода количество рукопожатий уменьшилось. Значит, для получения минимального числа рукопожатий количество людей в группах должно отличаться не более, чем на 1. Очевидно, нужно b групп сделать из a + 1 человека, а оставшиеся m - b групп сделать из a человек.

В этом случае количество рукопожатий получится равным

$b\cdot\dfrac{a(a+1)}2+(m-b)\cdot\dfrac{a(a-1)}2$

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

$\dfrac{(n-m+1)(n-m)}2$

рукопожатий.

Программа (python 3):

n = int(input())

m = int(input())

a, b = divmod(n, m)

print(b * a * (a + 1) // 2 + (m - b) * a * (a - 1) // 2)

print((n - m + 1) * (n - m) // 2)

Answer 2

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

1. Когда в каждой команде ровно по одному человеку: В этом случае, чтобы каждый человек пожал руку друг другу человеку в каждой команде, каждый человек должен пожать руку всем остальным в своей команде, кроме себя самого. Таким образом, минимальное количество рукопожатий будет равно количеству человек в каждой команде, а максимальное количество рукопожатий будет равно сумме количества человек во всех командах.

2. Когда в командах может быть разное количество людей: В этом случае оптимально будет сформировать одну команду с наибольшим количеством человек, чтобы минимизировать число рукопожатий. Максимальное количество рукопожатий будет таким же, как и в предыдущем случае.

Давайте теперь напишем программу, реализующую это:

pythonCopy code
def calculate_handshakes(n, m):
    # Когда в каждой команде ровно по одному человеку
    if m == 1:
        min_handshakes = n - 1
        max_handshakes = (n * (n - 1)) // 2
    else:
        # Когда в командах может быть разное количество людей
        # Минимальное количество рукопожатий достигается, когда одна команда собирает все людей
        # Максимальное количество рукопожатий также такое же, как и в случае, когда в каждой команде ровно по одному человеку
        min_handshakes = max_handshakes = n - m

    return min_handshakes, max_handshakes

# Ввод данных
n = int(input())
m = int(input())

# Вычисление и вывод результатов
min_handshakes, max_handshakes = calculate_handshakes(n, m)
print(min_handshakes, max_handshakes)

Программа получает на вход целые числа n и m и выводит два числа - минимальное и максимальное число рукопожатий, удовлетворяющих условиям задачи.