Московская городская олимпиада школьников по информатике,
2003/04 учебный год
при поддержке компаний
Задача D. Коллекционирование этикеток
| Имя входного файла: | d.in |
| Имя выходного файла: | d.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2,..., KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?
Формат входных данных
Входной файл содержит сначала число N - количество альбомов, а затем N чисел K1, K2,..., KN, задающих вместимости альбомов. N - натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.
Формат выходных данных
В выходной файл выведите сначала число E - максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел - каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
Пример
| d.in | d.out |
4 1 2 1 1 |
2 1 2 2 4 |