Помогите разобрать отельный случай задачи

Question

При m >= k, нужно найти C из n по k, но с такими ограничениями так нельзя :( как задачу можно решить без факториала ?

Текст задачи :

Егор хочет оформить свою гостиную в стиле постмодерн с элементами барокко. Дизайнер предложил ему оформить градиентное освещение – вставить в специальную нишу ровно k лампочек так, чтобы они шли в одну линию, а интенсивность света строго увеличивалась слева направо. Чтобы эта линия смотрелась плавно и гармонично, необходимо чтобы мощности лампочек увеличивались строго на единицу при переходе от одной лампочки к другой слева направо. Будем называть степенью освещенности помещения мощность последней лампочки в нише (то есть самой яркой).

Егор любит продумывать все варианты, поэтому ему стало интересно, сколько различных степеней освещенности можно получить, используя имеющиеся у него в запасе лампочки. Лампочки имеются двух видов — одни рассчитаны на определенную мощность, таких у Егора n штук, все их мощности известны, для i -й лампочки из этой категории она составляет w i . Вторую часть лампочек в количестве m штук Егору подарил дизайнер, который и был автором всей этой затеи. Эти лампочки можно отрегулировать под любую целочисленную мощность от 1 до 10 6 .

Помогите Егору и найдите, сколько различных уровней освещенности можно получить.

Формат входных данных В первой строке даны три числа — число лампочек у Егора n ( 1 ≤ n ≤ 10 6 ), число лампочек, подаренных дизайнером, m ( 1 ≤ m ≤ 10 6 ) и количество лампочек в нише k ( 1 ≤ k ≤ 10 6 ). Во второй строке даны мощности n лампочек, мощность i -й лампочки составляет w i Ватт ( 1 ≤ w i ≤ 10 6 ).

Формат результата Выведите единственное число — сколько различных уровней освещенности можно получить.

Примеры Входные данные

8 3 5
1 5 60 58 61 11 27 25

Результат работы

#include<iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef  unsigned long long ll;

    ll factorial(ll n) {
        ll res=1;
        while (n > 0) {
            res*=n;
            n--;
        }
        return res;
    }
int main() {
    ll n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(1000005);
    ll maxn = 0;
    for(int i = 1 ; i <= n;i++ ) {
        ll c;
        cin >> c;
        maxn = max(maxn , c);
        a[c]++;
    }
    if( m >= k) { \\Заменить этот кусок на что-то эффективное 
        ll pre = (factorial(9))/ ( factorial(k)*(factorial(9-k))); \\ C из n по k
        cout <<pre;
        return 0;
    }
    vector<ll> podsum(1000005);

    for(ll i = 1; i<= k;i++) {
        podsum[1] += a[i] ;
    }

    for(ll i = 2; i <= 1000005;i++) {
        podsum[i] = podsum[i - 1] - a[i - 1] + a[i + k - 1];
    }
    ll res = 0;
    for(int i = 1 ;i <=1000005;i++) {
        if (podsum[i] + m >= k) {
            res++;
        }
    }
    cout << res;

    return 0;
}

Answer 1

Если m>=k, то возможно создать непрерывную серию, кончающуюся на любое число из допустимого диапазона, поэтому в этом случае ответ 1000001 - k

Иначе нужно посчитать, сколько можно создать непрерывных серий, а для этого узнать, сколько в диапазоне end = k..1000000 (точнее, до значения maxlamp + k) существует скользящих окон длиной k с концом в end, содержащих не менее k-m лампочек традиционной ориентации.

В простейшем случае можно просто пройти в цикле по указанному диапазону. Если значение лампочки выходит из окна, уменьшить счётчик. Если входит - увеличить счётчик. Количество шагов, на которых счётчик >= k-m и есть решение.

При небольшом количестве обычных лампочек выгоднее, конечно, пройти только по тем местам, где они есть

Вот примитивное решение, оптимизация за автором.

n = 8
m = 3
k = 5
l = [1, 5, 60, 58, 61, 11, 27, 25]
a = set(l)
maxx = max(l)
if m >= k :
    print(1000001 - k)
else:
    count = 0
    res = 0
    l = 1
    for r in range(1, k+1):
        if r in a:
            count += 1

    #переберём правые концы интервалов длиной k
    for r in range(k+1, min(1000000, maxx + k + 1)): 
        if count >= k - m:   #добавив m универсальных ламп, заполним окно длиной k
            res += 1
        if l in a:    #обычная лампа выходит из интервала слева
            count -= 1
        if r in a:    #обычная лампа входит в интервал справа
            count += 1
        l += 1
    print(res)

БЛОГ НА HUSL

Помогите разобрать отельный случай задачи

Ответы (1 шт):