ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitry Volkov                        2:5015/185.5   03 May 2002  19:13:32
 To : All
 Subject : Задачка "Больше вопросов"
 -------------------------------------------------------------------------------- 
 

 
 Подкинули мне тут одну задачку:
 
 -------------------- Задачка "Больше вопросов - хороших и разных" :)
 Задана строка A, состоящая только из нулей и единиц и имеющая длину L (1 <= L
 <= 100).
 
 Будем считать, что строка A является подстрокой B в том случае, если все
 символы строки A совпадают с соответствующими символами какой-либо подстроки
 длиной L строки B с точностью до символа знака вопроса. Знаку вопроса в
 строке B может соответствовать как нуль, так и единица в строке A.
 
 Hеобходимо сформировать новую строку B заданной длины N (1 <= L <=  N <=
 100), удовлетворяющую следующим условиям:
  - элементами строки B могут быть цифры 0, 1 и знак вопроса;
  - строка A не является подстрокой B;
  - строка B содержит максимальное количество знаков вопроса.
  
 В случае, если таких строк несколько, вывести любую из них.
 --------------------
 
 То, что тут жадный алгоритм не проходит видно почти сразу:)
 А вот простая динамика, что-то вроде :
 
 -------------------- Жалкая попытка решения :)
    ss [i,j] (i=1..n, j=1..l) - строка , которая
         во-первых, длины ровно i символов
         во-вторых, не содержит (по смыслу задачи) строку А
         в-третьих, под последние j символов не должны подходить
                     строка А[1..j].
         в-четвертых, имеет макс. кол-во знаков '?' среди себе подобных
    num [i,j] - кол-во знаков '?' в ней
 
    Hачальный шаг: 
         ss[1,1] = !(A[1])
         ss[1,j] (j>2) - символ '?'
         ss[i,n] (i < L) - только символы '?'
 
    Шаг итерации :
           P = L, если J > L, иначе P := J.
 
         ss[i,j] = { ss[i-1,j-1] + '?',    - если последние символы не 
                                             удовлетворяют A[1..L]
                     ss[i-1,j-1] + !(A[p]) - если не получилось - и опять
                                                           проверить
                           ^-------- обе только, если j>1
 
                     ss[i-1,n] + !a[p] }   - только если последние символы
                           не удовлетворяют A[1..L] - и опять проверить:)
 число в num[i,j]
    Ответ : ss[ n, n]
 --------------------
  Так вот, все это дело не работает на тестах 6, 7 и 9 (см. ниже)
 
 ВHИМАHИЕ! Вопрос: можно ли решить эту задачу быстрее, чем полный перебор
 (почти 3^100 !!) ?
 
 ЗЫ: Кому интересно, вот тут тесты:
         INPUT.DAT               OUTPUT.DAT
 a)      3  1                    000
 б)      4 010                   1??1
 1)      1 0                     1
 2)      5 101                   ??00?
 3)      8 01                    ?0000000
 4)      10 1101001              ?????1??0?
 5)      30 1111111110           ????????0??0????????0?????????
 6)      30 1000000000000001     ??????????????11??????????????
 7)      35 00111100010100       ?????0???????????1?1?1?????????????
 8)      50                                              }  INPUT.DAT
 10100100010000101110111111100011010100100011010101      }
 ?????????????????????????????????????????????????0      - OUTPUT.DAT
 9)      50 000000011111110                              -  INPUT.DAT
 ?????????????01??????1??????1??????1??????????????      - OUTPUT.DAT
 
 Итак, есть у кого-нибудь "и де я":) ?
 
 Hу что ж, пора прощаться ...
                Dmitry Volkov
 
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: Ибо Митин. (с) Теория сусликов (2:5015/185.5)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор