Задача "модифицируемый ключ"
Многие вынуждены были чинить простой замок, от которого потерян ключ...
Это не такая сложная задача, выступы на ключе прижимают сдвигающиеся детали в замке
на определённое расстояние, делая возможным поворот.
<pre>
Это может выглядеть так (буква К - ключ, L - замок, '=' - граница, где поворот)
ККККККККККККККККККК
К ККК ККК ККК ККК
К К К К К
L L L L L
L L L L L
=======L===========
L L = L L
L L L L L
В данном случае замок открыть не удастся - средний выступ на ключе "утопил" движущуюся деталь
дальше, чем следует, и она перекрыла границу, однако, если мы удалим одно деление с выступа ключа,
"дав место" движущейся детали,
то замок откроется
ККККККККККККККККККК
К ККК ККК ККК ККК
К К L К К
L L L L L
L L L L L
===================
L L L L L
</pre>
понятно, что в упрощённом случае и замок и ключ можно представить в виде двух
массивов, в которых каждая ячейка показывает высоту выступа
(в целых единицах).
пусть массив, изображающий ключ, содержит РЕАЛЬНЫЕ высоты выступов,
а массив, изображающий замок - ТРЕБУЕМЫЕ (так проще)
понятно, что замок откроется, если соответствующие числа совпадут
23432
23432
такая комбинация ключа и замка откроет замок
а вот для такой
23532
23432
возникнет ситуация, когда средняя деталь "переутоплена" за границу поворота
и замок открыть не удастся.
Но и такая комбинация
23332
23432
создаст проблему - недоутопленная деталь также будет препятствовать вращению
ЗАДАЧА
Пусть у нас есть замок, представленный массивом байтов, содержащих числа от 1 до 8,
и ключ, представленный также массивом байтов; длина ключа больше длины замка - мы можем
произвольно перемещать ключ в замке в поисках подходящей комбинации,
также мы можем подпилить участок(-тки) ключа (на целое число единиц, разумеется), если подходящая
комбинация длин участков не найдена. Доращивать участки невозможно.
Построить алгоритм поиска открывающего замок участка ключа так, чтобы количество удаляемых
единиц с ключа было наименьшим (если найден точно подходящий к замку участок ключа, то количество
удаляемых единиц равно нулю).
Пример
для замка
1 1 1 2
и ключа
2 2 2 1 1 1 3
решение такое: открывающим будет участок ключа начиная с 3 ячейки (считая от 0)
при том, что ячейку 6 неоходимо спилить на 1 единицу.
предполагаемо даны
8 VALUE lock_len
CREATE lock x С, x С, x С, x С, x С, x С, x С, x С,
96 VALUE key_len
CREATE key x С, x С, x С, x С, x С, x С, x С, x С, [ 96 единицы ] ...
где х - произвольные числа от 1 до 8, длина массивов может быть другой, это не так существенно
необходимо закодировать слово
: key? ( lock lock_len key key_len --> position deleted true | false )
;
где position - позиция ключа, подходящая к замку,
deleted - количество подпиленных единиц
true | false - успех-неудача (если участок не нашёлся)
Задача "модифицируемый ключ"
Многие вынуждены были чинить простой замок, от которого потерян ключ...
Это не такая сложная задача, выступы на ключе прижимают сдвигающиеся детали в замке
на определённое расстояние, делая возможным поворот.
<pre>
Это может выглядеть так (буква К - ключ, L - замок, '=' - граница, где поворот)
ККККККККККККККККККК
К ККК ККК ККК ККК
К К К К К
L L L L L
L L L L L
=======L===========
L L = L L
L L L L L
В данном случае замок открыть не удастся - средний выступ на ключе "утопил" движущуюся деталь
дальше, чем следует, и она перекрыла границу, однако, если мы удалим одно деление с выступа ключа,
"дав место" движущейся детали,
то замок откроется
ККККККККККККККККККК
К ККК ККК ККК ККК
К К L К К
L L L L L
L L L L L
===================
L L L L L
</pre>
понятно, что в упрощённом случае и замок и ключ можно представить в виде двух
массивов, в которых каждая ячейка показывает высоту выступа
(в целых единицах).
пусть массив, изображающий ключ, содержит РЕАЛЬНЫЕ высоты выступов,
а массив, изображающий замок - ТРЕБУЕМЫЕ (так проще)
понятно, что замок откроется, если соответствующие числа совпадут
23432
23432
такая комбинация ключа и замка откроет замок
а вот для такой
23532
23432
возникнет ситуация, когда средняя деталь "переутоплена" за границу поворота
и замок открыть не удастся.
Но и такая комбинация
23332
23432
создаст проблему - недоутопленная деталь также будет препятствовать вращению
[b]ЗАДАЧА[/b]
Пусть у нас есть замок, представленный массивом байтов, содержащих числа от 1 до 8,
и ключ, представленный также массивом байтов; длина ключа больше длины замка - мы можем
произвольно перемещать ключ в замке в поисках подходящей комбинации,
также мы можем подпилить участок(-тки) ключа (на целое число единиц, разумеется), если подходящая
комбинация длин участков не найдена. Доращивать участки невозможно.
Построить алгоритм поиска открывающего замок участка ключа так, чтобы количество удаляемых
единиц с ключа было наименьшим (если найден точно подходящий к замку участок ключа, то количество
удаляемых единиц равно нулю).
Пример
для замка
1 1 1 2
и ключа
2 2 2 1 1 1 3
решение такое: открывающим будет участок ключа начиная с 3 ячейки (считая от 0)
при том, что ячейку 6 неоходимо спилить на 1 единицу.
предполагаемо даны
8 VALUE lock_len
CREATE lock x С, x С, x С, x С, x С, x С, x С, x С,
96 VALUE key_len
CREATE key x С, x С, x С, x С, x С, x С, x С, x С, [ 96 единицы ] ...
где х - произвольные числа от 1 до 8, длина массивов может быть другой, это не так существенно
необходимо закодировать слово
: key? ( lock lock_len key key_len --> position deleted true | false )
;
где position - позиция ключа, подходящая к замку,
deleted - количество подпиленных единиц
true | false - успех-неудача (если участок не нашёлся)
|