[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Общего плана ->Проблемы и их решения
Author Message
Aleksandr Losev

Topics: 27
Messages: 94

My Profile
Сегодня решал COCI16_R4 и столкнулся на 4-ой задаче с одной проблемой.

В чём заключалась задача? Было N(не дано в условии) арифметических прогрессий с первым членом 0 и разностью d[i] (для i-ой прогрессии). Взяли из этих прогрессий все члены от A до B включительно, отсортировали и дали различные.

Надо было найти N разностей, при которых, выполнив все действия, сказанные в условии, получился массив из входных данных. Числа были до 10 ^ 6 и имели максимум 5 знаков после запятой. Если существует несколько N разностей, вывести с минимальным N.

Короче, у меня была идея с жадностью. Типо переберём пару чисел из списка, возьмём их разность и проверим на корректность(не будет ли лишних чисел в прогрессии, если выписать от A до B. Потом перебирал каждое число, перебирал на сколько я буду его делить(от 1е5 до 1), если частное подходит под условие, добавим в список ответов и пропустим текущее число, которое перебрали(не частное). Дальше я убирал некоторые числа, которые можно получить через произведение какого-то другого числа на натуральное.

Под конец жадно набирать ответ. Пока у нас есть незакрытое число из прогрессии, берём ту разность, которая покрывает больше всех незакрытых чисел.

В итоге у меня вывело на сгенереном тесте кучу одинаковых чисел(я хранил в сете) и не убрали те, которые можно получить из других разностей путём домножения на натуральное. Я потратил часа два с половиной, чтобы решить эту проблему(но задачу я пока не сдал, вылезали какие-то баги из-за кривизны реализации и тп).

Так как знаков не больше 5-ти, я домножил все число на 10 ^ 5, чтобы убрать эту запятую, которая всё портит. Всё, проблема исчерпана, больше не нужно в коде возиться на этой ошибке, так как уже не будет никакой работы с дробными числами.
Mihail Dolinskiy

Topics: 1645
Messages: 39603

My Profile
Спасибо, Саша

Но лучше было кликнуть "Обсудить задач в форуме"
Я добавил туда ссылку на твои соображения
http://dl.gsu.by/NForum/posts/topicshow/3479.dl#last
 
Forum Index ->Общего плана ->Проблемы и их решения
Time:0,078