Александр Лосев
Темы: 30
Сообщений: 143
Мой профиль
|
Сегодня решал COCI16_R4 и столкнулся на 4-ой задаче с одной проблемой.
В чём заключалась задача? Было N(не дано в условии) арифметических прогрессий с первым членом 0 и разностью d[i] (для i-ой прогрессии). Взяли из этих прогрессий все члены от A до B включительно, отсортировали и дали различные.
Надо было найти N разностей, при которых, выполнив все действия, сказанные в условии, получился массив из входных данных. Числа были до 10 ^ 6 и имели максимум 5 знаков после запятой. Если существует несколько N разностей, вывести с минимальным N.
Короче, у меня была идея с жадностью. Типо переберём пару чисел из списка, возьмём их разность и проверим на корректность(не будет ли лишних чисел в прогрессии, если выписать от A до B. Потом перебирал каждое число, перебирал на сколько я буду его делить(от 1е5 до 1), если частное подходит под условие, добавим в список ответов и пропустим текущее число, которое перебрали(не частное). Дальше я убирал некоторые числа, которые можно получить через произведение какого-то другого числа на натуральное.
Под конец жадно набирать ответ. Пока у нас есть незакрытое число из прогрессии, берём ту разность, которая покрывает больше всех незакрытых чисел.
В итоге у меня вывело на сгенереном тесте кучу одинаковых чисел(я хранил в сете) и не убрали те, которые можно получить из других разностей путём домножения на натуральное. Я потратил часа два с половиной, чтобы решить эту проблему(но задачу я пока не сдал, вылезали какие-то баги из-за кривизны реализации и тп).
Так как знаков не больше 5-ти, я домножил все число на 10 ^ 5, чтобы убрать эту запятую, которая всё портит. Всё, проблема исчерпана, больше не нужно в коде возиться на этой ошибке, так как уже не будет никакой работы с дробными числами.
|