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

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

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

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

04.09.2013, 16:58. Просмотров 257. Ответов 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).
Если существует несколько способов собрать прямоугольник, то выведите любой.



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

Если у кого есть идеи, поделитесь плз. Заранее всем благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.09.2013, 16:58     Задачка на иниересную тему
Посмотрите здесь:

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

Задачка - C++
Помогите решить вот такую вот задачку: Получить все четырехзначные числа(1234,например),в которых не больше 2-х одинаковых цифр.Сколько...

задачка - C++
Добрый день,дорогие форумчане!Я битый час сижу над задачкой и никак не могу ее сделать...Надеюсь найдется тот,кто сможет сделать ее..буду...

задачка - C++
Дана последовательность чисел a1, …, an (N<20) и число K. Найти количество элементов имеющих значение меньше К, и количество элементов...

задачка с++ - C++
#include <iostream> using namespace std; int main() { int a;int i,j,z,y; cout<<"vvedite el-tu massiva:"; ...

Задачка по С++ - C++
#include <iostream> using namespace std; int main() { double x,z,n; int y; cout<<"vvedite summu="; cin>>x; cout<<"vvedite %...

Задачка C++ - C++
Помогите с еще одной, пожалуйста. Вот так вот выглядит: Z=(∏_(i=0)^7▒(m(i)-1) +∏▒〖(c(k)-5))/(〗 ∏_(j=0)^6▒K(j) -∏_(i=0)^7▒〖m(j)〗 Тут...

Задачка на C++ - C++
День Добрый. Такая ситуация, сижу на зачете, не могу решить простенькую задачку, помогите плз...вопрос моего допуска на экзамен :( ...

Задачка - C++
Здравствуйте, есть задачка: "Вводится строка, потом вводится символ. Далее нужно в строке убрать все эти символы, и сместить строку на...

задачка на с++ - C++
сделать таблицу размером N*N каждая строка и каждый столбец который содержит все числа от 1до N помогите не пойму как делать


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

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

P.S Но если меня просто заело на графах, то лучше, конечно, будет какой-нибудь алгоритм без них...
Ответ Создать тему
Опции темы

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