 |
|
Модераторы: Alx, Fixin |
 
|
|
Перфорация 
| OpenGL |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 30 Регистрация: 18.4.2008 Репутация: нет Всего: нет |
Очень интересная и сложная задача. Уже неделю пытаюсь решить ее, но
кроме перебора в голову ничего не приходит. http://icl.kazan.ru/turnir/contest/problem...0&contest=1 Все, у кого есть какие либо идеи, пожалуйста, помогите. Заранее спасибо. |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик  Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 2 Всего: 454 |
Формулировка задачи неточна, и допускает тривиальное решение - приклеить одну ленту в хвост второй.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| OpenGL |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 30 Регистрация: 18.4.2008 Репутация: нет Всего: нет |
Во первых, ленты бесконечны, во вторых, если так сделать, то не будет ни одной дырочки (ленты непрозрачны)
|
|||
|
||||
| SelenIT |
|
|||
 баг форума Профиль Группа: Завсегдатай Сообщений: 3996 Регистрация: 17.10.2006 Где: Pale Blue Dot Репутация: 4 Всего: 401 |
Имхо, на longest common subsequence смахивает...
-------------------- Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму! |
|||
|
||||
| Akina |
|
||||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 2 Всего: 454 |
В задаче длина лент ограничена
В задаче в лентах прорезаны дырки. Мы точно об одной и той же задаче говорим? -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
||||
|
|||||
| OpenGL |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 30 Регистрация: 18.4.2008 Репутация: нет Всего: нет |
Поэтому сообщение на ленте, скажем 01110010111011, можно представить как ...00001110010111011000... Если одна лента была 01110010111011, а другая 1001001001, то при наложении как в Вашем варианте получим: 0111001011101100000000000 0000000000000010010010010 ---------------------------------------- 0000000000000000000000000 ни одной дырочки. Максимальное количество дырочек в этом варианте будет: 011100101110110 000100100100100 ------------------------ 000100100100100 4 дырочки. |
|||
|
||||
| OpenGL |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 30 Регистрация: 18.4.2008 Репутация: нет Всего: нет |
Не понял  ))))))))) |
|||
|
||||
| SelenIT |
|
|||
|
баг форума Профиль Группа: Завсегдатай Сообщений: 3996 Регистрация: 17.10.2006 Где: Pale Blue Dot Репутация: 4 Всего: 401 |
Я имел в виду алгоритм поиска наибольших общих фрагментов, на нем diff основан. Но уже вижу, что тут задача несколько другая, буду думать еще...
-------------------- Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму! |
|||
|
||||
| OpenGL |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 30 Регистрация: 18.4.2008 Репутация: нет Всего: нет |
Спасибо за помощь, я уже нашел быстрый алгоритм
|
|||
|
||||
|
|
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
[ Время генерации скрипта: 0.0513 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |