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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
#1

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

04.09.2013, 16:58. Просмотров 271. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.09.2013, 16:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задачка на иниересную тему (C++):

задачка на тему строк - C++
Выписать из символьной строки слова, начинающиеся и заканчивающиеся на одну и ту же букву. помогите сделать пожалуйста...

Code:: Blocks (не на тему программирования, а на тему настройки) - C++
доброе время суток сразу попрошу прощения за созданную тему в этом разделе, которая не совсем по теме тут, но подходящей темы я не...

задачка на тему кинематика материальной точки - Механика
Материальная точка движется в плоскости xy по закону x= At; y= B/t, де А и В- положительные постоянные. Найти скорость V и ускорение А в...

Задачка с массивом и задачка с формулами Ньютона и Лагранжа - Fortran
Прошу помочь решить две задачи

Задачка так задачка - SQL Server
Здравствуйте, Ломаю голову, но ни как не могу прийти к решению. Задача следующая: К примеру есть некий адрес в столбце "624205,...

Сайт на тему cs 1.6 - Web-дизайн
Как вам ? Тематика: cs 1.6. Дизайн на тему: cs 1.6.

2
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,070
Завершенные тесты: 1
04.09.2013, 17:27 #2
во первых нужно создать функцию определения для каждого прямоугольника какой цвет какого размера
потом для одинаковых цветов во всех прямоугольниках сложить размеры, должно образоваться 4 разных числа, потом проверить что существует 2 эквивалентных пары (т.е две ширины и две высоты одинакового размера), если это условие не выполняется, то IMPOSSIBLE.... а вот как центральные прямоугольники считать это я не знаю)
1
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
05.09.2013, 13:33  [ТС] #3
Спасибо за ответ, но немного не понял, какие 4 числа должны получиться и такие задачи обычно (это базовая задача, просто я нет знаю, на какую тему) решаются одним универсальным алгоритмом (возможно просто алгоритм состоит из множества условий)...
Насколько я понимаю, здесь должен быть перебор вариантов компановок этих маленьких прямоугольников. Два прямоугольника могут соединяться только вершинами с 'N', помимо этого при их соединении справа и слева от вершины 'N' должны быть одинаковые цвета...
Но вот проблема в том, что я не могу уложить в голове это построение... Мало того там какие - то повороты... Очень напоминае теорию графов, но вот как реализовать, большой вопрос...

P.S Но если меня просто заело на графах, то лучше, конечно, будет какой-нибудь алгоритм без них...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2013, 13:33
Привет! Вот еще темы с ответами:

БД на тему библиотека - MS Access
Здраствуйте. Вот задали сделать бд, выбрала я бд на тему библиотека, сидела делала по видео урокам и различным сайтам. И зашла в тупик......

на Тему Энумов - Java SE
как создать с двух енумов: один 12 месяцев(Months) с параметром кол-во дней, а другой DaysOfWeek() в котором 7 дней --- возможность...

Оцените тему WP - WordPress
Здравствуйте. Активно осваиваю wordpress. Скачал psd макет простого лендинга и на его основе сделал вердпресс тему. Главная страница в виде...

Не отображает тему - WordPress
Добрый день! Вообщем у меня такая проблема, в cpanel в разделе site publishing выбрал одну из трех тем , потом зашел в wordpress и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.