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