IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Укладка плитки, Городская олимпиада
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


Недавно прошёл муниципальный тур олимпиады, там встертилась очень интересная задача)) Вот её условие:

Укладка плитки
Бригаде строителей поручили уложить квадратной плиткой пол на кухне в виде шахматного узора. Но строители работали не очень слаженно, и когда весь пол уже был уложен, оказалось, что в некоторых местах плитки одинакового цвета граничат друг с другом.
По заданному замощению определите, какое минимальное число строителей могло укладывать плитку.
Входные данные
Input.txt содержит восемь строк, состоящих из 8 символов W и B - полученное замощение (W - белый, B - ченрый).
Выходные данные
Output.txt нужно вывести искомое число строителей.

И пример к этой задаче:
WBWBWBBW
BWBBWBWB
WBWWBWBW
WBWWBWWB
BWBBWBWB
WBWBWWBW
BWBWBBWB
WBWBWWBW
Ответ 4 строителя.

Очень хотелось бы услышать методы решения задачи. Лично я делил всё замощение по 4 плитки и просматривал различные плитки... Но подобное решение не прошло.

Сообщение отредактировано: Сергей Меркурьев -


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Предполагается, что каждый строитель укладывает непрерывную область?
Ну тогда просто перекрась все чётные (у которых сумма координат чётная) клетки и посмотри число связных областей.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


Цитата
Предполагается, что каждый строитель укладывает непрерывную область?

Условие которое я дал, оно полное. Что же касается непрерывной области я не знаю smile.gif Сам гадаю, как могу.

Цитата
Ну тогда просто перекрась все чётные (у которых сумма координат чётная) клетки и посмотри число связных областей.

Не могли бы Вы поподробнее объяснить этот момент?


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Злостный любитель
*****

Группа: Пользователи
Сообщений: 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].


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


TarasBer, спасибо, попробуем разобраться с графами smile.gif


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Хорошая задачка. Условие только не совсем ясно поставлено.. Про непрерывность (более правильно, наверное - связность) приходится додумывать самому, исходя из примера. Скажем, может быть еще гипотеза, что у каждого рабочего своя не только связная, но и прямоугольная область. Но эта гипотеза отвергается из примера. Могут, наверное, быть и другие гипотезы. Лучше бы они все же сказали это более явно..

Добавлено через 6 мин.
хотя, впрочем, подумавши немного, я готов согласиться, что этого достаточно. Фразу:
Цитата
Но строители работали не очень слаженно
- можно толковать так, что каждый при укладке обращал внимание только на согласованность с плитками, уложенными им самим (как они их распознают потом - не важно). И тогда все становится на свои места smile.gif.

Все возражения снимаю. А задача еще поднимается в моих глазах good.gif.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


TarasBer, я проверил на 5 других тестах задачу, всё работает правильно.
А как можно придти к такому решению?)


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Ну я в детстве любил составлять кроссворды, и я заметил, что намного проще составлять их из слов, где чередуются гласные и согласные. И тогда получится, что если покрасить клетки кроссворда в зависимости от гласности буквы, то получится шахматная доска.
Потом я стал для интереса смотреть, где происходит разрыв шахматности, получил непрерывную линию, делящую кроссвод на несколько частей. Потому я стал количество таких линий считать одним из критериев качественности кроссворда.

Короче, ну не знаю я, как додуматься. Просто смотришь, что объединяет те плитки, которые проложил один человек, думаешь, прикидываешь, доходишь до ответа.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


mea culpa
*****

Группа: Пользователи
Сообщений: 1 372
Пол: Мужской
Реальное имя: Николай

Репутация: -  24  +


Цитата
каждый при укладке обращал внимание только на согласованность с плитками, уложенными им самим


Ну тогда например положил первый рабочий 4 плитки и ушел на перекур, подошел второй, который до этого ничего не клал, продолжать эту линию, на что ему ориентироваться и что класть? Они как-то между собой наверное согласовываться должны все же.

Сообщение отредактировано: Unconnected -


--------------------
"Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Unconnected @ 18.11.2010 14:33) *
Ну тогда например положил первый рабочий 4 плитки и ушел на перекур, подошел второй, который до этого ничего не клал, продолжать эту линию, на что ему ориентироваться и что класть? Они как-то между собой наверное согласовываться должны все же.

Не нужно забывать, что это все же абстракция.
Меня всегда радует, когда автору удается придумать хорошую проекцию "на реальную жизнь". Это на самом деле ОООЧЕНЬ непросто бывает. Но оно того стОит - решать веселее, проще с созданим образов.. Но излишнего углубления в реальность следует избегать. Иначе говоря, тут, например, рабочий - РАБОТАЕТ (а не ест, курит и т.п.) Работа сделана (все ЕГО плитки невозможно продолжить) - уходит.

Это тоже все очень важно. Это помогает потом абстрагироваться в действительно реальной (это тавтология?)) задаче.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Unconnected @ 18.11.2010 14:33) *
Они как-то между собой наверное согласовываться должны все же.
И еще один момент..
В условии сказано найти МИНИМАЛЬНОЕ возможное количество рабочих. Если, скажем, кто-то сверился с соседом - то его кладку от кладки соседа теперь не отличить. Это значит, что 2 рабочих превратились в 1 - то есть, общее количество рабочих уменьшилось. Поэтому, если они худо-бедно сверяются с соседями, то условие все равно при этом не нарушается.

А если рабочий начинает укладку в области, в которой слева один способ, а справа - другой, то он неизбежно присоединится к одному и законфликтует с другим. И снова условие задачи не нарушено и результат (при верном решении) будет верным.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Amoxicillin For Amoxil
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 2.12.2021 2:19
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name