ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Личное первенство УрГУ 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Разрезание окрашенного многоугольника

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Имеется выпуклый многоугольник, вершины которого окрашены в три цвета: красный (R), зеленый (G), либо голубой (B). При этом известно, что все три цвета точно присутствуют и никакие две соседние вершины не окрашены одинаково. Требуется выяснить, можно ли разрезать этот многоугольник непересекающимися диагоналями на треугольники так, чтобы у всех полученных треугольников была бы одна красная вершина, одна зелёная и одна голубая. Если это возможно, то требуется также указать возможный вариант разрезания.

Исходные данные

В первой строке содержится количество вершин многоугольника N (не менее 4 и не более 1000). Во второй строке находятся N символов из набора {R, G, B}, каждый из которых описывает раскраску цвет вершины многоугольника (в порядке обхода).

Результат

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

Пример

исходные данныерезультат
7
RBGBRGB
4
1 3
3 7
5 7
5 3
Автор задачи: Дмитрий Филимоненков
Источник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1181. Разрезание окрашенного многоугольника