Задачка "Больше вопросов"
- From
- Dmitry Volkov (2:5015/185.5)
- To
- All
- Date
- 2002-05-03T19:13:32Z
- Area
- RU.ALGORITHMS
Привет, многоуважаемый All,
Подкинули мне тут одну задачку:
-------------------- Задачка "Больше вопросов - хороших и разных" :)
Задана строка A, состоящая только из нулей и единиц и имеющая длину L (1 <= L
<= 100).
Будем считать, что строка A является подстрокой B в том случае, если все
символы строки A совпадают с соответствующими символами какой-либо подстроки
длиной L строки B с точностью до символа знака вопроса. Знаку вопроса в
строке B может соответствовать как нуль, так и единица в строке A.
Необходимо сформировать новую строку 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] - кол-во знаков '?' в ней
Начальный шаг:
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 (см. ниже)
ВНИМАНИЕ! Вопрос: можно ли решить эту задачу быстрее, чем полный перебор
(почти 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
Итак, есть у кого-нибудь "и де я":) ?
Ну что ж, пора прощаться ...
Dmitry Volkov
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: Ибо Митин. (с) Теория сусликов (2:5015/185.5)