0390. Шахматы

Кроме школы и математического кружка, Вася ходит на шахматный кружок. Но играть в шахматы на обычной доске 8 *8 ему кажется не очень интересным. Недавно он придумал свою версию шахмат, в которой игра происходит на доске, имеющей другую форму.

Васина доска состоит из n столбцов, i-й из которых содержит a_i клеток. Нижние клетки всех столбцов образуют один горизонтальный ряд, причем длины столбцов упорядочены слева направо по невозрастанию. На рисунке ниже приведен пример доски, в которой три столбца, содержащих 5, 2 и 1 клетку, соответственно.

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

Помогите Васе расставить на его доске минимальное число ладей требуемым образом.

Формат входного файла

В первой строке входного файла задано целое число n – количество столбцов доски (1 ≤ n ≤ 1000). Следущая строка содержит n чисел a₁, a₂, …, a_n – количество клеток в столбцах (1 ≤ a_i ≤ 1000, a₁ ≥ a₂ ≥ … ≥ a_n).

Формат выходного файла

В первой строке выведите число k – минимальное число ладей, которое можно расставить на доске так, чтобы каждую клетку доски била хотя бы одна ладья. Следующие k строк должны содержать описание позиций ладей, по одной на каждой строке. Позиция ладьи задается двумя числами: номером столбца, в котором стоит ладья, и номером клетки в столбце. Столбцы нумеруются, начиная с 1, слева направо, клетки в столбцах нумеруются снизу вверх, также начиная с 1.

Если подходящих расстановок несколько, можно вывести любую.

Пример:

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати