 Укладка плитки, Городская олимпиада |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Cheburashka |
 17.11.2010 13:47
Сообщение
#1
|
 Бывалый  Группа: Пользователи Сообщений: 195 Пол: Мужской Реальное имя: Сергей Репутация:  2   |
Недавно прошёл муниципальный тур олимпиады, там встертилась очень интересная задача)) Вот её условие:
Укладка плитки Бригаде строителей поручили уложить квадратной плиткой пол на кухне в виде шахматного узора. Но строители работали не очень слаженно, и когда весь пол уже был уложен, оказалось, что в некоторых местах плитки одинакового цвета граничат друг с другом. По заданному замощению определите, какое минимальное число строителей могло укладывать плитку. Входные данные Input.txt содержит восемь строк, состоящих из 8 символов W и B - полученное замощение (W - белый, B - ченрый). Выходные данные Output.txt нужно вывести искомое число строителей. И пример к этой задаче: WBWBWBBW BWBBWBWB WBWWBWBW WBWWBWWB BWBBWBWB WBWBWWBW BWBWBBWB WBWBWWBW Ответ 4 строителя. Очень хотелось бы услышать методы решения задачи. Лично я делил всё замощение по 4 плитки и просматривал различные плитки... Но подобное решение не прошло. Сообщение отредактировано: Сергей Меркурьев - 17.11.2010 13:48 -------------------- ♣♣♣
"Себя великим не считай, гордясь величьем предков, Величья не добудешь ты и золота ценою! Хоть светит на небе луна, но отраженным светом - Чужою славой не живи, не будь второй луною!!!" ♣♣♣ |
   |
 
|
  |
Ответов
| TarasBer |
17.11.2010 16:37
Сообщение
#2
|
 Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Ну было поле
01010101 10110101 01011010 10100101 01101011 11010100 Перекрасили все чётные клетки на противоположный цвет стало такое: 00000000 00011111 00001111 00001111 00111110 01111110 Тут 3 области (сам как-нибудь применишь стандартные алгоритмы обхода графа, чтобы понять, что их три). А вот пример из задания: 10101001 01001010 10110101 10110110 01001010 10101101 01010010 10101101 Перекрашиваем, получаем 11111100 11100000 11100000 00011100 00011111 00000111 00000111 00000111 тут 4 области. На самом деле про перекраску я для наглядности сказал. Просто сделай обход исходного графа, в качестве условия связности клеток возьми A[i1,j1] <> A[i2,j2]. -------------------- |
|
|
|
Сообщений в этой теме
Сергей Меркурьев Укладка плитки 17.11.2010 13:47
TarasBer Предполагается, что каждый строитель укладывает не... 17.11.2010 14:08 Сергей Меркурьев
Условие которое я дал, оно полное. Что же касаетс... 17.11.2010 16:27 Сергей Меркурьев TarasBer, спасибо, попробуем разобраться с графами... 17.11.2010 16:51 Lapp Хорошая задачка. Условие только не совсем ясно по... 18.11.2010 2:59 Сергей Меркурьев TarasBer, я проверил на 5 других тестах задачу, вс... 18.11.2010 13:17 TarasBer Ну я в детстве любил составлять кроссворды, и я за... 18.11.2010 14:03
Unconnected
Ну тогда например положил первый рабочий 4 плитк... 18.11.2010 14:33 Lapp Ну тогда например положил первый рабочий 4 плитки ... 19.11.2010 0:05 Lapp Они как-то между собой наверное согласовываться до... 19.11.2010 1:09 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.07.2025 10:57 |