Д🍋
только я выше поправил
что у нас не точка а интервал тут
что у нас не точка а интервал тут
если что
"отрезки" наши просто массив int
те время тут интовое
Size: a a a
2020 March 21
Д🍋
MB
Ну это не важно
Д🍋
[1, 4] — процесс который выполняется во времени 1 2 3 4 грубо говоря
MB
только я выше поправил
что у нас не точка а интервал тут
что у нас не точка а интервал тут
А я написал, что сделать так, чтобы решать для ненулевого отрезка
Д🍋
То есть мы хотим понять: есть ли на интервале (a,b) точка, покрытая менее чем k отрезками из набора. Давай каждый отрезок разделим на два события: начало и конец.
События отсортируем по координате и будем по ним идти, поддерживая счетчик открытых отрезков (видим событие начала - делаем +1; видим событин конца - делаем -1).
Пусть мы для какой-то точки обработали все события начала отрезка, относящиеся к ней.
Если счетчик > K, то текущий набор уже некорректен.
Если счетчик <K, и эта точка лежит в допустимом интервале, то мы победили: вставим новый нулевой отрезок сюда
События отсортируем по координате и будем по ним идти, поддерживая счетчик открытых отрезков (видим событие начала - делаем +1; видим событин конца - делаем -1).
Пусть мы для какой-то точки обработали все события начала отрезка, относящиеся к ней.
Если счетчик > K, то текущий набор уже некорректен.
Если счетчик <K, и эта точка лежит в допустимом интервале, то мы победили: вставим новый нулевой отрезок сюда
ну да
кажется это будет работать
спасибо
а есть ли тип задач какой-то вот подобный?
кажется это будет работать
спасибо
а есть ли тип задач какой-то вот подобный?
MB
ну да
кажется это будет работать
спасибо
а есть ли тип задач какой-то вот подобный?
кажется это будет работать
спасибо
а есть ли тип задач какой-то вот подобный?
Задачи на "отрезочки"
Д🍋
Спасибо в общем
решение и правда простое.
решение и правда простое.
2020 March 22
V
Всем привет. Есть тут одна задачка не могу никак придумать алгоритм. Есть уравнение X1+X2+...+Xn= C, n натуральные . Нужно вывести все возможные варианты решения.
(Пример: С=5 N=3
311
113
131
221
212
122)
(Пример: С=5 N=3
311
113
131
221
212
122)
V
И С, N<=50
EZ
Всем привет. Есть тут одна задачка не могу никак придумать алгоритм. Есть уравнение X1+X2+...+Xn= C, n натуральные . Нужно вывести все возможные варианты решения.
(Пример: С=5 N=3
311
113
131
221
212
122)
(Пример: С=5 N=3
311
113
131
221
212
122)
Ну рекурсивно заполнять решение
EZ
Но их может быть очень много
V
Количество решений можно получить по формуле С с (с-1) по (н-1)
V
Не состыковка получается при С=6 н=4
3111
1113
1131
1311
2211
2112
1122
1221
1212
2121
3111
1113
1131
1311
2211
2112
1122
1221
1212
2121
V
Последние два варианта нельзя получить с помощь сдвига в право одного елемента
EZ
Последние два варианта нельзя получить с помощь сдвига в право одного елемента
Ват
V
Ну тип там через один
f
Где то видел это, на динамику. Сейчас поищу
DE
Где то видел это, на динамику. Сейчас поищу
На динамику вроде все разбиения
V
В каком смысле на динамику ?