Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Задачка на иниересную тему - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Отсортировать массив методом вставки http://www.cyberforum.ru/cpp-beginners/thread948298.html
#include <conio.h> #include <iostream.h> #include <math.h> main() // oboznacheniya peremennih { int n,//kolichestvo elementov ishodnogo massiva m,//kolichestvo elementov massiva znacheniy...
C++ Консольное приложение. Матрицы.Написать и протестировать функции Написать и протестировать функции вычитания матриц, изменения знака матрицы, формирования единичной матрицы, умножения матрицы слева на ее транспонированную, перестановки двух столбцов матрицы,... http://www.cyberforum.ru/cpp-beginners/thread948288.html
Процедуры и массив (создать, заполнить, вывести, подсчитать количество неубывающих серий) C++
Помогите написать программу. Нужны создать массив ( к примеру 10 элементов) и несколько процедур к нему. 1. Заполнить массив. 2. Вывести его 3. Подсчитать количество неубывающих серий ( т.е...
C++ Направьте на путь истинный!)
Здравствуйте господа и леди форума) Начал я изучать язык программирования с++, выбрал книжку для новичка " Р.Флюре." Ооп в с++, она наверно не для новичка я даже и не знаю)) Но вся соль в том что ни...
C++ сумма элементов матрицы http://www.cyberforum.ru/cpp-beginners/thread948244.html
С клавиатуры вводится размерность целочисленной матрицы,затем сама матрица.Найти сумму всех элементов.Разрешается при этом использовать только один оператор цикла(кроме цикла ввода матрицы). Вот...
C++ перемешать матрицу Вобщем нужен только сам цикл который бы перемешивал все элементы в матрице случайным образом,хотя бы идею как это реализовать то подробнее

Показать сообщение отдельно
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43

Задачка на иниересную тему - C++

04.09.2013, 16:58. Просмотров 266. Ответов 2
Метки (Все метки)

Доброго времени суток.

Решаю олимпиадные задачи по программированию, наткнулся на описанную ниже задачу и не могу понять, с какой стороны к ней подойти...

Текст задачи:

Через прямоугольник, все четыре стороны которого раскрашены в разные цвета, провели несколько разрезов, параллельных его сторонам. После этого получившиеся маленькие прямоугольники перемешали и, возможно, несколько раз повернули на 90 градусов по часовой стрелке.

Ваша задача — восстановить прямоугольник, если это возможно. Заданные прямоугольники разрешается вращать по часовой стрелке на 90 градусов от 0 до 3 раз. Два маленьких прямоугольника в собранном прямоугольнике могут иметь общую сторону только в том случае, если эта сторона бесцветна. В собранном прямоугольнике должны быть использованы все заданные маленькие прямоугольники, ничего не должно остаться. Стороны собранного прямоугольника должны быть раскрашены в различные цвета, каждая сторона в свой цвет.

Входные данные

Первая строка входного файла содержит одно целое число N — количество имеющихся маленьких прямоугольников (1 ≤ N ≤ 103).
Следующие N строк задают маленькие прямоугольники. Каждый прямоугольник описывается на отдельной строке. Его описание состоит из последовательности, содержащей два целых числа w и h, за которыми идут четыре буквы c0, c1, c2 и c3, записанные через пробел. w и h задают ширину и высоту прямоугольника (1 ≤ w, h ≤ 105), а буквы — цвета сторон его в порядке обхода по часовой стрелке, начиная с верхней стороны прямоугольника. c[j] может принимать значения {R, G, B, Y, N} (0 ≤ j ≤ 3), где R, G, B, Y — цвета сторон исходного прямоугольника, а N обозначает отсутствие цвета.

Выходные данные

Если восстановить прямоугольник, используя все заданные прямоугольники, невозможно, то в выходной файл нужно вывести единственную строку IMPOSSIBLE.
В противном случае необходимо вывести N строк, которые описывают положение заданных маленьких прямоугольников в собранном прямоугольнике в порядке их перечисления во входном файле. Совместим начало координат с левым нижним углом собранного прямоугольника, ось OX пойдет по нижней его стороне, а ось OY — по левой вертикальной стороне. Тогда каждая строка будет содержать описание положения одного маленького прямоугольника в результирующем. Описание должно состоять из трех целых чисел, записанных через пробел. Первые два числа x и y задают координаты левого нижнего угла соответствующего прямоугольника в собранном прямоугольнике, а третье число r — количество его вращений по часовой стрелке (0 ≤ x, y ≤ 105, 0 ≤ r ≤ 3).
Если существует несколько способов собрать прямоугольник, то выведите любой.



Вот думал, каким образом её решать... Может через графы, но тогда что выбрать за вершины и каким образом обходить? Можно перебором, но тут никак в голове не складывается картина логики перебора((

Если у кого есть идеи, поделитесь плз. Заранее всем благодарен.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru