Python
Робин Бобин Барабек
думает, сколько коров и быка он съест на обед. Он берет шестнадцатеричное число. За одно действие он может заменить один из знаков на соседний (0 заменить на 1 или F, А заменить на 9 или В и т. п.). Он ставит себе ограничение сверху на количество действий и старается максимизировать количество подслов BEEF. Ваша программа в первой строке ввода получает последовательность цифр от 0 до 9 и букв от А до F. Всего не более 100000 знаков. Во второй строке написано ограничение на число ходов. Оно не превышает 1000. Программа должна напечатать максимальное число подслов BEEF, которое можно получить, не превышая максимального числа ходов.
https://codeshare.io/2pdOB0
Код на Си. Работает по крайней мере на примерах, данных выше, и в примитивных случаях BEE1 2, ABC 100, BE 0 и др. которые несложно было проверить вручную.
Вот та часть решения, которое я еще могу объяснить:
Для начала создадим функцию, которая для заданного 4-значного 16-ричного числа определяет минимальное количество действий, которое необходимо с ним совершить, чтобы оно стало числом BEEF. По-факту на ЯП это будет какая-то функция numberOfActions(c1,c2,c3,c4), которая принимает 4 символа c1,c2,c3,c4 и возвращает целое число (попробуйте написать ее сами, если не получится - пишите в комментарии).
Обозначим строку, данную по условию - s, ее длину - n, максимальное количество действий - h.
Создадим массив A на n целых чисел.
В ячейку A[0] запишем количество действий, которые необходимо совершить c числом S[0],S[1],S[2],S[3], чтобы привести его к виду BEEF.
В ячейку A[1] запишем количество действий, которые необходимо совершить c числом S[1],S[2],S[3],S[3] чтобы привести его к виду BEEF.
И так далее аналогично.
По-факту нужно будет сделать цикл
for (i = 0; i <= N-4; i++)
A[i] = numberOfActions(S[i], S[i+1], S[i+2], S[i+3])
Теперь если выбрать какое-либо 4-значное число из строки S, которое начинается на месте S[i], то мы будем точно знать, сколько действий нужно совершить, чтобы привести это число к виду BEEF (а именно их нужно совершить A[i] штук).
Теперь из массива A[i] нужно выбрать максимально возможное количество чисел таких, чтобы их сумма не превышала L, причем между этими числами в массиве должно быть не менее 3 других (объяснять это долго, попытайтесь самостоятельно понять).
Тут пошло динамическое программирование.
(конец)
ДП поясняется очень сложно, пояснение долгое и во многом там нужно понимать интуитивно (по крайней мере для меня это так).
Код на Си. Работает по крайней мере на примерах, данных выше, и в примитивных случаях BEE1 2, ABC 100, BE 0 и др. которые несложно было проверить вручную.
Вот та часть решения, которое я еще могу объяснить:
Для начала создадим функцию, которая для заданного 4-значного 16-ричного числа определяет минимальное количество действий, которое необходимо с ним совершить, чтобы оно стало числом BEEF. По-факту на ЯП это будет какая-то функция numberOfActions(c1,c2,c3,c4), которая принимает 4 символа c1,c2,c3,c4 и возвращает целое число (попробуйте написать ее сами, если не получится - пишите в комментарии).
Обозначим строку, данную по условию - s, ее длину - n, максимальное количество действий - h.
Создадим массив A на n целых чисел.
В ячейку A[0] запишем количество действий, которые необходимо совершить c числом S[0],S[1],S[2],S[3], чтобы привести его к виду BEEF.
В ячейку A[1] запишем количество действий, которые необходимо совершить c числом S[1],S[2],S[3],S[3] чтобы привести его к виду BEEF.
И так далее аналогично.
По-факту нужно будет сделать цикл
for (i = 0; i <= N-4; i++)
A[i] = numberOfActions(S[i], S[i+1], S[i+2], S[i+3])
Теперь если выбрать какое-либо 4-значное число из строки S, которое начинается на месте S[i], то мы будем точно знать, сколько действий нужно совершить, чтобы привести это число к виду BEEF (а именно их нужно совершить A[i] штук).
Теперь из массива A[i] нужно выбрать максимально возможное количество чисел таких, чтобы их сумма не превышала L, причем между этими числами в массиве должно быть не менее 3 других (объяснять это долго, попытайтесь самостоятельно понять).
Тут пошло динамическое программирование.
(конец)
ДП поясняется очень сложно, пояснение долгое и во многом там нужно понимать интуитивно (по крайней мере для меня это так).
Делай итерацию своей строки. Найди символы A,B или С - это потенциальная буква B и начинай "рыть" от нее дальше, в поисках D, E или F - это потенциальная буква E, потом ищи следующую E и заканчивай символами E, F или 1 - это может быть буквой F.
Вот тебе и первый вариант BEEF. Затем от этой же B - ищи следующие варианты EEF. Затем ищи следующую B - и так до конца количества действий.
Вот тебе и первый вариант BEEF. Затем от этой же B - ищи следующие варианты EEF. Затем ищи следующую B - и так до конца количества действий.
Бека Сеннин
59 552
Александр Леонов
да спасибо
Александр Тодинов
Но напишите пожалуйста без кода словесный алгоритм что требуется сделать
Похожие вопросы
- У Робин Гуда, Робинзона.. . И Робин-бобин Барабека.. . Дружить домами нет резона? Ведь, все ж, три разных человека...
- И всё же кто же Робин Бобин Барабек ?
- робин бобин на английском языке русскими буквами
- Кто такой Робин-Бобин?
- Какую балладу о Робин Гуде лучше прочитать на урок мировой литературы? (или несколько)
- Переведите плз текст на английский язык про Робин Гуда. Срочно надо!!!!
- Про Робин Гуда
- Конан Дойл, Робин Гуд, Дон Кихот...
- РОБИН ГУД …. для чего он надевал ---КАПЮШОН ???
- Бобинный (катушечный) магнитофон Юпитер МК-106С - как его подключить к компьютеру, чтобы переписать песню с бобины?
вот моя почта
luasor@mail.ru
напишите мне туда или скиньте свою почту, и я потом сообщу свой телеграм
Я еще про графы задачу протестировал при входных данных 3 1 оно не должно ничего выводить
https://mega.nz/file/Hz4UQCrY#GGYrQGXxCuvoWRAQLmPcOTiBH4lb_ylDo8y9wnXgcFM