Задача № 3 Перед тобой расписание тренировок Скриптоши на 12 дней. Каждый день занят одним из трёх типов упражнений. Профессор хочет изменить расписание так, чтобы робот…
Задача № 3 Перед тобой расписание тренировок Скриптоши на 12 дней. Каждый день занят одним из трёх типов упражнений. Профессор хочет изменить расписание так, чтобы робот тренировал один и тот же навык по нескольку дней подряд. Так у него будет больше шансов на успех. В расписании разрешается заменить не больше трёх дней. Какие из них надо поменять, чтобы робот максимально долго тренировал один навык без перерыва? Закрыть Если забудешь, как выглядит исходное расписание, можешь взглянуть на эту картинку.
Пожалуйста, пришли саму раскладку на 12 дней (или изображение). Я по ней дам конкретные дни, которые нужно поменять.
Чтобы ты понимал, как это решается и как я найду ответ, вот подробный план и шаги вычислений (без конкретной раскладки пока что):
Как решить задачу шаг за шагом
- Пусть есть три типа упражнений, назовём их A, B, C. Раскладка S содержит 12 символов из {A, B, C}, по порядку дней 1…12.
- Цель: сделать максимально длинную непрерывную последовательность одного типа X (X ∈ {A, B, C}) за счёт замены не более 3 дней на X.
- Идея: для каждого типа X ищем наибольший отрезок [l, r], в котором количество дней не равных X не превышает 3. Тогда можно поменять эти несовпадающие дни на X, и получится непрерывный блок X длины (r − l + 1). Этот блок даёт максимальную возможную длину блока X с учетом ≤3 замен.
- Алгоритм (скользящее окно):
- Для каждого X в {A, B, C} запусти окно [l, r], начав с l = 1, r = 1.
- Подсчитывай count_not_X — число дней внутри окна, не равных X.
- Удвояй правую границу r от 1 до 12. Если S[r] ≠ X, увеличь count_not_X.
- Пока count_not_X > 3, сдвигай левую границу l вправо: если S[l] ≠ X, уменьшай count_not_X; l++.
- После каждого шага обновляй максимум длины окна: best_len_X = max(best_len_X, r − l + 1) и запоминай, какое окно дал этот максимум (best_l, best_r).
- Данные по всем трём X выбирают наилучший результат: максимальное best_len_X среди X ∈ {A, B, C}.
- Какие дни менять
- Возьмём лучший блок [best_l, best_r] для выбранного X.
- В нём поменяй на X все дни, где S[i] ≠ X. Это не более 3 дней по условию.
- Этот набор дней — ответ на вопрос, какие именно дни поменять.
Полезные примеры и нюансы
- Если таких окон несколько, можно выбрать любое с максимальной длиной.
- Важно: мы меняем конкретно те дни внутри блока, которые не совпадают с выбранным навыком X.
- В случае отсутствия входных данных я не смогу указать конкретные номера дней. Пришли, пожалуйста, 12 символов (например: A B C A A B C A B C A B) без пробелов, или изображение — я посчитаю и дам точный ответ.
Готов приступить к расчёту сразу после того, как ты пришлёшь расписание. Если хочешь, могу также привести пример на наглядном наборе данных, чтобы показать, как именно выбираются дни для замены.
