Здравствуйте, пользователи CodeForces. Сегодня прошел первый этап Всесибирской олимпиады школьников по программированию. Таблицы результатов до сих пор нет, но зато каждый лично видит на сколько баллов он написал свои задачи. Расскажите как решить на 100 вторую задачу и третью (тут явно динамика, но я не понимаю как правильно ее написать).
UPD. Опубликован рейтинг в системе тестирования всех участников.
Мне тоже интересна 3я. Но мне вот сейчас в голову пришла такая мысль: может, в условии они не зря написали про точность вычислений и мы можем считать динамику для long double: минимальное и максимальное произведение, изменив первые i элементов и потратя на это j операций сложения.
Прямую ссылку на условия можно? Сайт немного ужасен.
http://zalil.ru/33935965
2: геометрия с листочка.
3:
a) Проверим, что мы можем набрать хотя бы 0. Если не можем, то плюсуем наибольшее отрицательное сколько можем и выводим. (т.к. жадно уменьшаем модуль).
b) Переберем сколько чисел ответа будут положительными, при этом отрицательных должно быть четное число. Заметим, что делать положительными выгодно наибольшие из отрицательных (трогать отрицательное, которое не станет положительным, не выгодно; затем a<=0, b<=0: |a|(b+j) — (a+j)|b| = (|a|-|b|)j отсюда видно, что наилучший модуль достигается при изменении наибольшего отрицательного). Сделаем их 1 сразу (вычтем необходимое из k). Теперь нам дан набор положительных чисел, надо сделать из них наибольшее. Легко показать, что надо каждый раз увеличивать наименьшее число.
с) Из полученных в пункте b выбираем наилучшее (в даблах).
Итоговая сложность max(N*K,N^2) (при большом желании N^2, если последнее из b делать через бинпоиск)
"Геометрию с листочка" ни один человек не написал на 100.
н_и_ один
однако у меня есть мысль как её решить, если зайдет на ~100 в дорешку, выложу код
Там 100% точность не меньше extended / long double. Требуемая точность ужасна. Кроме того, я бы в целых числах проверял все особенные случаи.
А нельзя ли в заголовок добавить "школьная"? А то через пару дней начинается "XIII Открытая Всесибирская олимпиада по программированию им. И.В.Поттосина".