:

Timus Online Judge. Задача GTimus Online JudgeАнглийскийРусскийOnline JudgeО системеПослать на проверкуАрхив задачСостояние системыОбсудитьЧАВОСсылкиАвторыЗарегистрироватьсяИсправить данныеРейтинг авторовСоревнованияТекущееРасписаниеАрхивG. Разрезание окрашенного многоугольникаОграничение времени: 1.0 секундыОграничение памяти: 16 МБИмеется выпуклый многоугольник, вершины которого окрашены в три цвета: красный (R), зеленый (G), либо голубой (B). При этом известно, что все три цвета точно присутствуют и никакие две соседние вершины не окрашены одинаково. Требуется выяснить, можно ли разрезать этот многоугольник непересекающимися диагоналями на треугольники так, чтобы у всех полученных треугольников была бы одна красная вершина, одна зелёная и одна голубая. Если это возможно, то требуется также указать возможный вариант разрезания.Исходные данныеВ первой строке содержится количество вершин многоугольника N (не менее 4 и не более 1000). Во второй строке находятся N символов из набора {R, G, B}, каждый из которых описывает раскраску цвет вершины многоугольника (в порядке обхода). РезультатВ первой строке должно содержаться количество проведённых диагоналей, если требуемое разрезание возможно, либо число 0, если разрезание невозможно. В случае, когда разрезание возможно, в следующих строках должно содержаться описание диагоналей, по которым проводится разрез. Описание одной диагонали занимает одну строку и состоит из пары номеров вершин, которые соединяет данная диагональ, разделенных пробелом. Если для данного многоугольника существует несколько вариантов разрезания, удовлетворяющих условиям, то достаточно указать любой из них.Примерисходные данныерезультат7 RBGBRGB4 1 3 3 7 5 7 5 3 Автор задачи: Дмитрий ФилимоненковИсточник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002Версия для печати    Статистика    Обсудить    Послать на проверку© 2000-2007 The Team. Все права защищены. sharp ar-5415 :