Есть последовательность чисел.
Допустим 1,5,6,8,12,14,18,20

Развернем ее в чистый числовой ряд
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

Нужно разбить эту последовательность на группы чисел, одинаковой длины так, чтобы
А) Было как можно больше групп в которых все числа серые
Б) Самих групп было бы как можно меньше

Вообщемто нужно найти длину такой оптимальной группы чисел.
Для примера - длина группы равна 5.

1,2,3,4,5 |
6,7,8,9,10 |
11,12,13,14,15 |
16,17,18,19,20

Яростный МечМетод МайороваДля примера - длина группы равна 5.

1,2,3,4,5 |
6,7,8,9,10 |
11,12,13,14,15 |
16,17,18,19,20 странный пример.
С одной стороны, нет ни одной полностью "серой" группы, с другой - можно было бы разбить на меньшее число групп, напр., по 10 чисел в каждой

Ну вот нужно найти компромисс, найти такой период чтобы было как можно больше серых групп с одной стороны и при этом таких групп было как можно меньше.

AklinМетод МайороваА) Было как можно больше групп в которых все числа серые
Б) Самих групп было бы как можно меньше

что главней ???
два противоречащих друг другу условий.


первое что приходит на ум - посчитать среднюю длинну серых групп, серо-черных групп...

Критерий есть.
Все полностью серые группы можно принять как 0.
Все остальные группы как 1.
Таким образом лучшее решение с самим меньшем коэфициентом.

Например.
Период: 5.
Количество групп: 10
Количество полностью серых групп: 3
Не серых: 7

Таким образом 3*0+7*1 = 7

Метод МайороваAklinпропущено...


что главней ???
два противоречащих друг другу условий.


первое что приходит на ум - посчитать среднюю длинну серых групп, серо-черных групп...

Критерий есть.
Все полностью серые группы можно принять как 0.
Все остальные группы как длина группы.
Таким образом лучшее решение с самим меньшем коэфициентом.

Например.
Период: 5.
Количество групп: 10
Количество полностью серых групп: 3
Не серых: 7

Таким образом 3*0+7*5 = 35

ошибочко там была.

Есть еще один важный ньюанс.
Последовательность может быть любой
например 1, 45, 500000, 1212454545

и решение по памяти критично, нельзя разворачивать последовательность в памяти или делать это както ограничено

Вес у группы равно длине этой группы.
Вес полностью серой группы равен 0.

Penkov Vladimirв целых числах - тупой перебор (o(n))


нужно чтото попытаться придумать без тупого перебора :(

Penkov VladimirМетод Майоровапропущено...


нужно чтото попытаться придумать без тупого перебора :(

зачем? пробежать по массиву придется при любом алгоритме. так что o(n) вам не преодолеть.

просто бежать не получится, память критична
10842622

т.е. это нужно сделать както хитро вычитаниями или хз

Короче тут два критерия, с памятью допустим можно чтото придумать.
Но нужно придумать чтото с эвристикой.

Например если элементов будет 1 млн.
то решение перебором будет (1млн * на пробежаться по 1 млн) тоесть уже миллиард.
А это недопустимо.

Метод МайороваКороче тут два критерия, с памятью допустим можно чтото придумать.
Но нужно придумать чтото с эвристикой.

Например если элементов будет 1 млн.
то решение перебором будет (1млн * на пробежаться по 1 млн) тоесть уже миллиард.
А это недопустимо.

тьху, здесь не миллиард а 1млн^2