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

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


 

Башенки из кубиков

(Время: 2 сек. Память: 64 Мб Сложность: 42%)

Маленький Рома любит играть в кубики и строить из них башенки. Всего у него N кубиков, каждый из которых определяется целочисленным размером Ai, который определяет длину ребра i-го кубика. Если поставить несколько кубиков последовательно друг на друга, то получается башенка.

Рома считает башенку красивой, если каждый последующий сверху вниз кубик имеет размер на единицу больше, чем предыдущий. Высота башенки – это количество кубиков в ней. То есть для красивой башенки высоты M, состоящей из кубиков с размерами S1, S2, …, SM, должно выполняться условие: Si-1 = Si – 1 для i от 2 до M.

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

Помогите Роме с этой задачей!

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

Первая строка входного файла INPUT.TXT содержит число N – количество кубиков у Ромы (1 ≤ N ≤ 2×105). Во второй строке содержатся N целых чисел A1, A2, …, AN , где Ai – размер i-го кубика (1 ≤ Ai ≤ 2×105).

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13
1 2 3
1
1 3
25
6 2 3 2 1
3
1 3
2 2
6 6

Система оценки

Решения, работающие только для N ≤ 100, будут оцениваться в 40 баллов.

Решения, работающие только в тех случаях, когда размеры всех кубиков различны, будут оцениваться в 40 баллов.


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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Винни-Пух
 B. Игра в 8
 C. Треугольник в прямоугольнике
 D. Поход за грибами
 E. Башенки из кубиков
 F. Весёлые качели
 G. Площадь многоугольника
 H. Мирные ладьи

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru