источник - • УБИЙЦА ОТРЕЗКОВ НА PYT... ↓ЗАПИСЫВАЙСЯ НА ЗАНЯТИЯ↓ Telegram t.me/evgenrepp Inst / evgen.rep VK evgenrep
Пікірлер: 6
@leoshastin5 ай бұрын
Концепция хорошая, но слишком громоздкая, потому мне более каноничным кажется решение через проверку точек с дробным шагом, тогда не нужна разбивка на 4 случая. Есть пару мыслей о том, как можно упростить этот способ решения: 1. Нет смысла выполнять проверку для х, лежащих далеко за пределами начала самого левого отрезка и конца самого последнего отрезка (самой маленькой и самой большой точки в points), ведь нам достаточно проверить по одной точке из каждой области (условно область 1023..1362, область 1362..1813 и т.д., области начал и концов тех или иных подотрезков на числовой прямой), а потому с лихвой хватит взять диапазон проверки от минимальной и до минимальной точек из points (и -1 и +1 на случай с подвохом, когда нужно учесть область ЗА ПРЕДЕЛАМИ всех данных отрезков, чтобы уж точно всё учесть); 2. Вместо разбивки на 4 случая можно поработать с дробными числами, а именно рассмотреть, например, для отрезка [1023; 2148] точки 1022.9, 1023.1, 2147,9, 2148.1 - их будет достаточно для всех 4 подслучаев (таким же образом нужно рассмотреть и другие отрезки, уже из них собрать общий список points). Когда points таким образом будет сконструирован, можно будет ограничиться одной проверкой, не нужно пугать школьников вложенными списками, тем более в №15. Код в целом будет лаконичнее, я полагаю, а идея проще (и для объяснения тоже) Над реализацией мне думать лень, но можно что-нибудь с генераторами и мапом начудить, чтобы быстро и красиво все эти дробные точки получить. Если получится из этого что-нибудь собрать, тогда с радостью посмотрю на уже доработанную версию) ВОТ ТОГДА уже, если правда получится упростить до одной лишь проверки с концептом дробных точек, этот способ правда будет лучше (ибо эффективнее, очев)
@evgenrep5 ай бұрын
Привет, спасибо! 1. Да, я в начале сказал, что мы можем не делать эти проверки, можно действительно брать range меньше, но на эффективность данного алгоритма это не сильно влияет, ничего страшного, если мы переберем так много точек)) 2. Если работать с дробными числами, то традиционно может выдаться ответ в формате 1022.9 и тд, то есть тут ещё нужно осознать, что это действительно интервал/полуинтервал, а может и вообще так, что начальная и конечная точка будут 1023.1, 2147.9. Данная идея уже рассмотреть много где, в частности видел одно интересное решение vt.tiktok.com/ZSFLtBMjG/ Но оно не работает на всех задачах. Концепт дробных точек много где используется, но он не даёт конкретный ответ на задачу, в любом случае может быть погрешность. Опять же, можно добавить доп. проверки на десятичную часть и округление, но снова добавляем новое. В данном случае, я считаю, что этот способ всё-таки "солвер", так как выдаёт конкретный ответ на любую задачу. Касаемо эффективности, конечно, она почти квадратичная, но точек у нас немного, поэтому алгоритм работает достаточно быстро.
@leoshastin5 ай бұрын
@@evgenrep round корректно округлит все случаи с дробным ответом - где нужно вверх и где нужно вниз - разве есть контрпримеры? Не встречал) как раз потому для меня решение на дробных точках с round 100% солвер, на ≈ 50-100 задач ни одной осечки
@evgenrep5 ай бұрын
@@leoshastin если ты про видео, которое я скинул из тиктока, то есть один контрпример конкретно для него: №4875 с Полякова. А так, я не сомневаюсь, что с округлением будет солвер, я это и написал, просто там нужно дополнительно понимать эти моменты округления. То есть, каков бы ни был солвер, всё равно нужно учитывать какие-то нюансы. Либо округление, либо то, что это может интервал/полуинтервал.
@user-ul4mn6lr2k4 ай бұрын
зачем писать такой огромный код, можно еще проще, этот код оставил в том видео в комментариях
@evgenrep4 ай бұрын
Потому что это солвер, он решает любой прототип независимо от условия. Тут просто пишешь код и всё)