Поучаствовали с Мишкой в очередном соревновании. Я успел решить первые две задачи и не успел отправить решение по третьей. После завершения соревнования решение третьей оказалось правильным.
Решение второй задачи у нас с Мишкой оказались одинаковыми, и мы оба получили "неправильный ответ на претест 3". Пока ломаю голову, при каких условиях может не сработать...
С первой задачей у Мишки оказалось всё плохо - он не прошёл по времени. Видимо, у Питона действительно есть серьёзные проблемы с математикой. Я же схитрил и тупо наполнял StringBuilder символами.
Удалось придумать, как решить вторую задачу?
ОтветитьУдалитьПохоже, там логика нетривиальная.
Не-а
УдалитьМожно посчитать текущую страшность (то есть сумму всех холмов и долин, назовём их выступ, далее нам не важно, какой выступ, так как все выступы будут чередоваться холм-долина-холм...). А дальше стоит рассмотреть варианты, как моно уменьшить страшность. Самый простой способ уменьшить страшность - это сделать выступ равным соседнему элементу массива.
УдалитьНайдём максимальное улучшение, которое можно вычесть из текущей страшности
1. Если нет выступов, то улучшения не нужно
2. Если есть одиночный выступ, то улучшение = 1
3. Если есть двойной выступ (вершина-холм - соседние элементы массива), то улучшение = 2 в случае, если приравнивание холма к вершине или вершины к холму даст выигрыш в 2 (иначе улучшение = 1).
То есть надо оценивать не только текущие выступы, но и состояние массива после двух потенциальных улучшений (не появятся ли в других местах новые выступы).
4. Если есть тройной выступ (холм-вершина-холм), то улучшение = 3
Больше 3 улучшение быть не может.
Это непростая логика со сложным анализом.
Есть более простое решение. Просто заменять каждый элемент массива на соседний и смотреть, что получится.
Вот пример кода:
https://codeforces.com/contest/1467/submission/103761330
А тут в каментах можно форматирование кода сделать? А картинки прикрепить?
ОтветитьУдалитьСкорее нет, чем да
Удалить