Директор школы доверил провести линейку учителю математики, но тот воспринял это задание буквально и выстроил всех учеников школы в одну длинную линию. Увидев это директор решил оценить такое построение, вычислив две характеристики: Болтливость построения. Директор предположил, что ученики одного класса будут болтать между собой. Поэтому его интересует суммарное попарное расстояние между учениками одинаковых классов. Задирчивость построения. Директор предположил, что ученики разных классов будут задирать друг друга. Поэтому его интересует суммарное попарное расстояние между учениками разных классов. Ваша задача — вычислить болтливость и задирчивость построения. Замечание В примере болтливость складывается из расстояний: |1 − 4| + |2 − 3|, а задирчивость — из расстояний: |1−2|+|1−3|+|2−4|+|3−4|. Формат входных данных Первая строка содержит одно целое положительное число K (1 <= K <= 105) — число классов в школе. Следующая строка содержит одно целое положительное число N (1 <= N <= 105) — число учеников в школе, которые пришли на линейку. Следующие N строк содержат описания учеников участвующих в линейке. Каждая из этих N строк содержит описание одного ученика: два целых числа x и y (|x| <= 107,1 <= y <= K) — положение ученика и его класс. Формат выходных данных В первой строке выведите одно целое число — болтливость построения. Во второй строке выведите одно целое число — задирчивость построения. Пример 1 Входные данные 2 4 1 1 2 2 3 2 4 1 Выходные данные 4 6

Давайте разберем задачу шаг за шагом и приведем решение.

Задача:
У нас есть учеников, каждый ученик находится в определенной позиции x и принадлежит к определенному классу y. Все ученики выстроены в линию по их координате x. Нам нужно посчитать:

• Болтливость — сумму попарных расстояний между учениками одного класса.
• Задирчивость — сумму попарных расстояний между учениками разных классов.

Что нужно сделать:

1. Считать число классов K.
2. Считать число учеников N.
3. Для каждого ученика записать его позицию x и класс y.
4. Обработать учеников по классам, чтобы найти:
   • сумму попарных расстояний внутри каждого класса (болтливость).
   • сумму попарных расстояний между учениками разных классов (задирчивость).

Основные идеи:

• Болтливость (одинаковый класс):
  Для каждого класса нужно вычислить сумму попарных разностей. Можно упростить:
  Для множества учеников x1, x2, ..., x_m у каждого класса, сумма попарных расстояний равна:

  [ \sum_{i<j} |x_j - x_i| ]

  Можно решить быстрее, отсортировав учеников этого класса по координате x. Тогда:

  [ \sum_{i<j} (x_j - x_i) ] так как x_j >= x_i, и абсолютное значение пропадает.

  Формула для подсчета суммы попарных разностей после сортировки:

  Пусть отсортированные координаты: X = [x_1, x_2, ..., x_m]

  Тогда:

  [ \text{Sum} = \sum_{i=1}^{m} x_i \cdot (i-1) - \sum_{i=1}^{m} x_i \cdot (m - i) ]

  Через префиксные суммы это можно сделать быстрее.

• Задирчивость (разные классы):
  Нужно найти сумму попарных расстояний между всеми учениками двух разных классов.
  Изначально можно подойти так:
  Посчитать сумму всех попарных расстояний между всеми учениками, а затем вычесть сумму внутри каждого класса (то есть сумму внутриодноклассных расстояний).
  Но это не очень просто, если не учитывать повторные подсчеты и большое количество учеников.

Эффективный подход:

1. Для каждого ученика запомним x и y.

2. Создадим два массива:

   • массив positions для подсчета внутри каждого класса.
   • массив all_positions для подсчета всех учеников в целом.

3. Для подсчета внутри класса:

   • Для каждого класса соберите все позиции учеников, отсортируйте их.
   • Посчитайте сумму попарных расстояний по формуле.

4. Для подсчета между классами:

   • Можно использовать следующую идею:
     • После подсчета всех учеников и сортировки, можно стремительно собрать сумму всех расстояний между всеми учениками (общая сумма), также используя префиксы.
     • Тогда за счет вычитания внутренне классовых расстояний получим сумму для заказанных наборов.

Но легче всего — использовать суммы:

• Объявим переменную total_sum — сумму расстояний между всеми учениками.
• Собрав всех учеников и отсортировав их по x, мы можем определить total_sum так:

[ \text{total_sum} = \sum_{i=1}^{N} (x_i \times (2i - N - 1)) ]

где (x_i, y_i) — отсортированные по x.

Затем:

• Для каждого класса посчитаем внутреннюю сумму (сумма внутри одного класса).
• Заменим сумму между разными классами:

[ \text{разные_классы} = \text{total_sum} - \sum_{\text{класс}} \text{внутреннюю сумму класса} ]

Итоговая реализация:

• Читаем входные данные.
• Собираем для каждого класса список позиций x.
• Находим сумму попарных расстояний внутри класса.
• Считаем сумму всех попарных расстояний между всеми учениками.
• Вычисляем болтливость и задирчивость по формулам.

Код решения (на Python):

import sys
input = sys.stdin.read

def main():
    data = input().split()
    K = int(data[0])          # число классов
    N = int(data[1])          # число учеников
    students = []
    index = 2
    for _ in range(N):
        x = int(data[index])
        y = int(data[index + 1])
        students.append((x, y))
        index += 2

    # Собираем позиции по классам
    classes = [[] for _ in range(K + 1)]
    for x, y in students:
        classes[y].append(x)

    # Сортируем позиции внутри каждого класса
    for c in range(1, K + 1):
        classes[c].sort()

    # Функция для подсчета суммы попарных расстояний внутри одного массива
    def sum_of_pairwise_differences(arr):
        prefix_sum = 0
        result = 0
        for i, val in enumerate(arr):
            result += val * i - prefix_sum
            prefix_sum += val
        return result

    # Болтливость — сумма попарных расстояний внутри каждого класса
    boltivost = 0
    # Общая сумма попарных расстояний между всеми учениками
    # Для этого отсортируем всех учеников по x
    students_sorted = sorted(students, key=lambda c: c[0])
    all_x = [x for x, y in students_sorted]
    total_sum = 0
    prefix_sum = 0
    for i, x in enumerate(all_x):
        total_sum += x * i - prefix_sum
        prefix_sum += x

    # Подсчет суммы внутри каждого класса
    internal_sum = 0
    for c in range(1, K + 1):
        internal_sum += sum_of_pairwise_differences(classes[c])

    # Болтливость — сумма внутри класса
    boltivost = internal_sum

    # Задирчивость — сумма между всеми учениками минус сумма внутри классов
    zadirchivost = total_sum - internal_sum

    print(boltivost)
    print(zadirchivost)

if __name__ == "__main__":
    main()

Итоги:

• Вывод — это два числа:
  • Болтливость (сумма попарных расстояний внутри классов).
  • Задирчивость (сумма попарных расстояний между учениками разных классов).

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