Задача D. Армия дроидов ≡

Условие

Торговая Федерация славится своей не очень эффективной военной силой — армией дроидов.

Армия дроидов состоит из N полков, i-й из которых содержит a_i рот по b_i дроидов в каждой. Для повышения огневой мощи и боевой эффективности (если это вообще возможно) руководство Торговой Федерации решило реорганизовать армию.

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

Генерал Гривус хочет определить минимально возможную абсолютную разницу между полками, а также предложить новый план распределения дроидов.

Абсолютной разницей двух целых чисел называется разница, посчитанная по модулю. Например, |5 − 2| = |3| = 3 или |2 − 5| = | − 3| = 3.

Требуется написать программу, которая по текущим данным об армии дроидов определит наилучший вариант реорганизации.

Формат входных данных

Первая строка содержит одно целое число N — количество полков в армии дроидов.

Далее следует N строк, i-я из которых содержит два целых числа a_i и b_i — количество рот в i-м полку и количество дроидов в одной роте этого полка соответственно.

Формат выходных данных

Первая строка должна содержать одно целое число — минимально возможную абсолютную разницу количества дроидов между полками.

Далее должно быть выведено N строк, i-я из которых содержит два целых положительных числа — новое количество рот в i-м полку и новое количество дроидов в одной роте этого полка соответственно.

Если ответов несколько, разрешается вывести любой из них.

Ограничения

2 ≤ N ≤ 10⁵

1 ≤ a_i, b_i ≤ 10³

Описание подзадач и системы оценивания

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

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснения к примерам

В первом примере, после реорганизации, количество дроидов в первом полку составит 16, а во втором полку — 15.

Примеры тестов

2
3 7
2 5

1
4 4
3 5

3
6 5
4 6
3 18

0
6 6
4 9
3 12

Разбор

Полное решение

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

Решение напрашивается быстро: достаточно оставить в каждом полку всего 1 (т.е. a_i = 1) роту, в которую будем помещать нужное в этом полку количество дроидов.

Теперь необходимо выбрать количество дроидов в каждом полку. Чтобы минимизировать абсолютную разницу между ними, нужно выбрать N максимально равных между собой чисел. Такое количество (обозначим его mid) равно mid = cntN, где cnt = a₁ ⋅ b₁ + a₂ ⋅ b₂ + ...  + a_N ⋅ b_N (т.е. общее число дроидов).

Если cnt делится на N нацело, то во всех ротах будет mid дроидов и минимальная абсолютная разница между ними равна 0.

Если cnt не делится на N нацело, то необходимо найти остаток от деления (обозначим его как k, cnt = mid ⋅ N + k). Чтобы «нейтрализовать» этот остаток (мы не можем просто так выкидывать дроидов), необходимо распределить дроидов по полкам. Выгоднее всего добавить по 1 дроиду в любые k различных полков (то есть k рот будут иметь mid + 1 дроидов, а оставшиеся N − k будут иметь mid дроидов), тогда минимальная абсолютная разница между полками будет равна 1. Нетрудно доказать, что это всегда возможно, так как остаток от деления всегда меньше знаменателя (k < N).

Частичные решения

Стоит обратить внимание на ограничения N, a_i, b_i, так как максимально возможное cnt = a_max ⋅ b_max ⋅ N_max = 10³ ⋅ 10³ ⋅ 10⁵ = 10¹¹, что превышает 2 * 10⁹ (максимальную вместимость 32-битных типов данных).

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