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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105

1 ≤ ai, bi ≤ 103

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N
1 66 2 ≤ N ≤ 102
2 34 2 ≤ N ≤ 105 1

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

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

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

Стандартный вход Стандартный выход
1
2
3 7
2 5
1
4 4
3 5
2
3
6 5
4 6
3 18
0
6 6
4 9
3 12

Разбор

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

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

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

Теперь необходимо выбрать количество дроидов в каждом полку. Чтобы минимизировать абсолютную разницу между ними, нужно выбрать N максимально равных между собой чисел. Такое количество (обозначим его mid) равно mid = cntN, где cnt = a1 ⋅ b1 + a2 ⋅ b2 + ...  + aN ⋅ bN (т.е. общее число дроидов).

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

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

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

Стоит обратить внимание на ограничения N, ai, bi, так как максимально возможное cnt = amax ⋅ bmax ⋅ Nmax = 103 ⋅ 103 ⋅ 105 = 1011, что превышает 2 * 109 (максимальную вместимость 32-битных типов данных).

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

Подзадача Дополнительные ограничения Оценка времени работы решения
N
12 ≤ N ≤ 102O(N2) — какое-нибудь квадратичное решение или O(N) без учета возможного переполнения
22 ≤ N ≤ 105O(N) — решение с использованием 64-битных типов данных


0.079s 0.014s 13