Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Зарплата - 2

(Время: 1 сек. Память: 16 Мб Сложность: 43%)

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

Короче, творится полный бардак. И чтобы этот бардак уменьшить, Самый Главный Начальник решил использовать недавно принятый закон «о материальной помощи», который позволяет любому сотруднику часть своей зарплаты (целое число рублей от 1 до d-1) передавать другому сотруднику в виде материальной поддержки. Однако по закону сотрудник, таким образом, может «помогать» только одному «малоимущему».

Например, если Петя и Вася получают по 100 рублей и Петя напишет заявление на передачу 30% своей зарплаты Васе, то Петя будет получать 70 рублей, а Вася - 130.

Теперь Самый Главный Начальник хочет узнать: кто, кому и сколько должен передавать, чтобы в результате все получали ровно столько, сколько нужно. Помогите ему это сделать.

Входные данные

Входной файл INPUT.TXT содержит целые числа n и d (1 ≤ n ≤ 105, 1 ≤ d ≤ 109), и далее n целых чисел di (1 ≤ di ≤ 109). Сумма всех di равна n∙d.

Выходные данные

В выходной файл OUTPUT.TXT выведите n пар целых чисел ai и bi, означающих, что сотрудник i передает сотруднику ai часть своей зарплаты в размере bi рублей. Если сотрудник i ничего никому не передает, выведите вместо ai и bi два нуля.

Примеры

INPUT.TXTOUTPUT.TXT
13 200
100
300
200
2 100
0 0
0 0
23 200
10
300
290
3 190
0 0
2 100

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483