Задача про полоски с дырками

[waxtep]

anahronizm в сообщении #1718359 писал(а):

Стало интересно попробовать описать все не проколотые элементы при любом заданном количестве вилок. И не обязательно такими вилками, как в задаче.
Вот Вы показали, как можно описать все не проколотые клетки если вилка одна. Удобна ли такая запись при вычислении не проколотых элементов ?
Или вот задача: предположим, что у нас есть бесконечная полоска. И по ней прошлись первой и второй вилкой по два раза (как условие в задаче). Как выразить все не проколотые элементы на этой бесконечной полоске? Да так, чтобы такая запись была удобна для использования, например, вычисления всех не проколотых элементов на заданном интервале.
А если берётся только вторая и третья вилка с их двумя проходами ? Или только пятая, седьмая и восьмая ?
Было бы здорово записать общую формулу.

Тут, к сожалению, формула не обещает быть удобной: по сути, придется вычислить все проколотые разными вилками клетки, и сказать, что "а не проколотые - это все остальные".
Можно попробовать переформулировать задачу как найти возможность (или доказать невозможность) представления функции, не меньшей единицы в целых точках отрезка в виде суммы периодических функций на этом же отрезке, но я не уверен в продуктивности такого подхода. (Типа, прокол - единичка, отсутствие прокола - нолик, и суммируем такие "вилкопроходные" функции на отрезке).

anahronizm в сообщении #1718359 писал(а):

Но, скорее всего, не рассматривали отдельно, например, вилки 2 и 3 или вилки 3,4 и 6.

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

Ничего толкового пока для пяти и более вилок мне выжать не удалось, хотя старался я очень, в том числе, пытаясь жульничать и подглядывать Даже для четырех уже так себе: совсем быстро считающий вариант дает максимум $34$ клетки, а уже не очень-то быстрый - $38$; это при известной стратегии, позволяющей проколоть $41$ клетку подряд. Для пяти, шести вилок разница по сравнению с известными стратегиями, дающими $71, 126$ проколов, - еще драматичнее (хуже работает). Для семи и более вилок, соответственно, тоже ничего интересного (зато можно довольно быстро посчитать ). Хочется попробовать формализовать, что нужно максимизировать "на полпути" для достижения оптимального (или, по крайней мере, "очень хорошего") результата в конце, но пока не умею. А без разбиения на такие блоки, задача выглядит гробовой в силу астрономического количества вариантов уже для совсем малого количества (до десяти) вилок