Как найти количество вариантов получения числа из последовательности чисел?

Дана последовательность чисел. Например: 2 9 3 6 3 8 1 10 6 7.

Нужно узнать: сколькими способами можно образовать число, большее 8. При чем есть важное условие: если мы уже добились того, что комбинация больше 8 (3+3+3=9), то дополнять комбинацию новыми числами уже нельзя (3+3+3+5 - нельзя, ведь 3+3+3 - уже > 8).

Правильные ответ - 42, но я никак не могу понять как его добиться.

Я понимаю, что можно перебирать последовательность (2+9, 2+3+3, 2+...) и смотреть, больше 8 или нет, но это слишком долго. Я гуглил уже комбинаторику, но вот не нашел решение. Поэтому обратился сюда.

Подскажите формулу или толкните в нужном направлении.
  • Вопрос задан
  • 3729 просмотров
Пригласить эксперта
Ответы на вопрос 4
gbg
@gbg
Баянист. Тамада. Услуги.
Генерируете все сочетания, суммируете, сравниваете.

Гуглил он, называется...
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Напрашивается сортировка по возрастанию, затем рекурсивный перебор с отсечением по критерию.
2 | 9 | 3 | 6 | 3 | 8 | 1 | 10 | 6 | 7
Сортируем
1 | 2 | 3 | 3 | 6 | 6 | 7 | 8 | 9 | 10

функция перебор(numbers, result, summ) {
    пока numbers не пуст {
        current = numbers[0]; // первое число
        numbers = numbers[1..]; // остаток массива
        если summ+current > 8 
            вывести result, current;
        иначе
            перебор(numbers, [result | current], summ+current);
    }
}
перебор([1 | 2 | 3 | 3 | 6 | 6 | 7 | 8 | 9 | 10], [], 0);
Ответ написан
Mrrl
@Mrrl
Заводчик кардиганов
Да, задача не имеет вообще ничего общего с тем, что вы написали вначале. Надо найти число подотрезков - то есть, фрагментов последовательности без пропусков. Ограничения "нельзя удлинять отрезок, если сумма достигла M+1" у них нет - они говорят только, что можно и не удлинять. То, что "воспользуемся модулем", не означает, что надо брать сумму модулей - иначе ответ был бы около 50. Вероятно, имеется в виду, что модуль суммы должен быть больше M (из примера этого понять нельзя, в нём нет отрезка с суммой меньше -8).
Могу сказать, что задача совсем непростая. Грубой силой она не решается (требуется N^2/2 сравнений, в секунду не уложитесь).
Я бы делал так. Взять массив частичных сумм (0, a0, a0+a1, ...). Потом сделать log_2(N) копий этого массива (занумерованных индексом k от 1 до log_2(N)), и в каждом из них отсортировать отрезки длиной 2^k. Для массива из задачи это будет выглядеть так:
S0=S[0]=[0,-2,7,10,16,19,27,26,36,30,37]
S[1]=[-2,0, 7,10, 16,19, 26,27, 30,36, 37]
S[2]=[-2,0,7,10, 16,19,26,27, 30,36,37]
S[3]=[-2,0,7,10,16,19,26,27, 30,36,37]
К сожалению, массивы S[1],S[2],S[3] оказались одинаковыми - это потому, что в примере мало отрицательных чисел.
Имея такие массивы, вы легко ответите на вопрос "сколько чисел в фрагменте массива S0[k+1]..S0[N] не принадлежат диапазону S0[k]-M .. S0[k]+M" (время - log(M)^2). Сумма таких ответов для всех k от 0 до M-1 и даст ответ на задачу. Полное время - M*log(M)^2.
UPD. Лучше бы они писали условие по-английски. Было бы не так стыдно за формулировку.
Ответ написан
@Saymon_K Автор вопроса
В связи с тем, что появились недопонимания условия выкладываю оригинал (надо было это сделать сразу)

31cec0f810904ec8b7fb12bfeac25f90.png
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы