Сап б, недавно встретился с задаче и не могу понять как ее грамотно решить, в чем суть:Есть числа a,b,c,d, это координаты отмечающие 2 линии, с a по b b с-d соответственно.1 линию необходимо уменьшить или не трогать, а 2 увеличить или не трогать. Но линии не могут накладываться друг на друга и сумма их длин не должна изменятся.Задача в том, что бы посчитать кол-во возможных перестановок.Пример - 2 пик, снизу изначальные позиции 2-4 и 6-8, а сверху 5 возможных вариантов перестановок. Так при a=2, b=4, c=6, d=8 ответ 5.Кто нибудь знает алгоритм как это рассчитать? Я сижу и не могу догадаться, думаю надо идти в сторону того, что бы посчитать кол-во возможных вариантов без ограничений и потом вычитать кол-во вариантов отсеченных условиями. НО, я не представляю как посчитать кол-во перестановок допустим 1 линии, думал это факториал, но нет.В общем, помогите придти к решению, с меня как всегда.
>>211731791 (OP)система уравнений:(b-a)+(d-c)=4b=/=cдругое дело, что двигать то можно до бесконечности и тебе нужен максимум для d
>>211733126Бля я еблан, извиняйте, еще 2 условия забыл вписать1.Новое a-b должно содержаться в старом a-b2.Новое c-d должно содерждать в себе старое c-d
>>211733532>>211733598Есть две линии, надо посчитать кол-во возможных перестановок(т.е. увеличение или уменьшение линий на какое-то значение) выполняющих условия:1.Линия a-b может только уменьшается2.Линия c-d только увеличиваться3.Линии не могут накладываться друг на друга4.Новая линия a-b должна находиться полностью на старой линии a-b(т.е. вот мы уменьшаем линию 2-4, мы не можем уменьшить ее длину например до 1-2)5. Новая линия c-d должна содержать в себе старую линию c-d( т.е. если у нас 6-8 линия, мы не можем увеличить ее так, что бы она стала 5-7 например)6.Общая длина длин не должна измениться ( т.е. если мы уменшаем первую на 1, мы должны увеличить вторую на 1)
>>211733502олимпиадная комбинаторика класс за 10-11, можешь попробовать залететь в какой нибудь олимпиадный паблик впараше и попросить математиков решить там, они любят с таким ебатьсямимо бывший олимпиадник
>>211734422Такая же хуйня, но я вот тоже на комбинаторику думаю, но никак не могу выкупить как это все посчитать правильно
>>211734317и тебе>>211734422там не так много теории в комбе, но достаточно чтобы непросвещенный вообще не вдуплял что происходитможете просто открыть разбор любой комбы с какого нибудь физтеха 2015, чтобы понять что она довольно таки нетрудная, просто банально опыта нетhttps://www.youtube.com/watch?v=K3BYLuPv_dc
>>211734883Кароче почитал по комбинаторике и выкупи формулу для вычисления кол-ва возможных перестановок a-b линии:(n+1)!/2*(n-1)!
>>211735675Извиняй братан, но я забыл еще 2 условия в ОП-посте написать:1.Новая линия a-b должна находиться полностью на старой линии a-b(т.е. вот мы уменьшаем линию 2-4, мы не можем уменьшить ее длину например до 1-2)2. Новая линия c-d должна содержать в себе старую линию c-d( т.е. если у нас 6-8 линия, мы не можем увеличить ее так, что бы она стала 5-7 например)
>>211733961Вот такое решают в 10-11 классе? Ебать я тупой походу, хотя люблю залипать в задачи и загадки.
>>211735946Лицеисты и олимпиадники да, в последние 10 лет идет неумолимый рост сложности технопредметов, я рад что смог поступить в такое время, когда еще не дают задачи с межнаров на обычных перечнеолимпах и технари не круглые сутки ботают, а имеют возможность хотя бы погулять и поесть
>>211737276Неплохо, но если число там длина их под миллиард? Долго переберать будет, мне кажется лучше через формулу
>>211737679https://ideone.com/cPku18миллиард не получится, но десяток четверть миллиарда норм выходитесли бы линии могли накладываться и выходить за 0 и 10 могла бы получиться простая красивая формула которую я бы осилил прочухать а так сорь
>>211738531Короч формула такая: f1(l1,l2) - f2(l1,l2,c-b) - f3(l1,l2,c,t)f1 (все варианты включая то что наложилось и вылезло) легко начухатьf2 (то что наложилось) чуть сложнееf3 (то что вылезло) ещё сложнее
>>211739230Я думал вот над чем, я понял как вычислить кол-во вариантов перестановок линии a-b пик, сумма арифметическое прогрессии в общем-то, так же еще идея в том что длиня c-d не важна, потому что если взять, допустим бесконечное расстояние между аб и сд, то мы получим что кол-во возможных вариантов по идеи должно равняться аб! /(ab-1)!, по идеи это должоно работать потому что аб может уменьшиться или в право или в лево, сд тоже либо в право либо в лево, на тогда, когда аб уменьшается ровно на то же кол-во делений, а нужно нам знать еще бс, если бс>аб-1, то сд может увеличиваться как хочешь, а если аб-1>бс тут уже надо вычислить кол-во вариантов которое бс собой перекрывает.
>>211739230https://ideone.com/F4WtvFf1(l1o,l2o) = 4l1ol1ol1o/3 + 3l1ol1o/2 - 2l1o(l1ol1o/2 + l1o/2) + l1o/6где l1o = b - a(убрал проверки, упростил код и посчитал в sympy питоном)https://repl.it/repls/NotedTatteredScales
>>211741521Добра, но либо я кривожопый, либ что, но при 5-8 и 11-13, я насчитал только 11 перестановок
>>211731791 (OP)Если бы ты нормально условие написал, я бы тебе набросал код, но я так почитал тред, ты проебался с условием, че-то там забыл, я ебал в этом всем разбираться. Учись составлять пост нормально.
