0390. Шахматы

Input file name: chess.in
Output file name: chess.out
Time limit: 2 s
Memory limit: 256 megabytes

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

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

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

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

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

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

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

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

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

Пример:

chess.inchess.out
3 5 2 1 2 1 5 2 1


Source: Karelian school team championship. November 2014.

Discuss       Submit a solution



Printable version