Оптимизация задачи

Question

Есть такая задача:

Я попытался её сделать так:

#include <iostream>
using namespace std;

bool check(int a, int b, int c){
    return a < b + c && b < a + c && c < a + b;
}

int main() {
    int a, b, c, d, count = 0;
    cin >> a >> b >> c >> d;
    for (int x = a; x <= b; x++){
        for (int y = b; y <= c; y++){
            for (int z = c; z <= d; z++){
                count += check(x, y, z);
            }
        }
    }
    cout << count;
}

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

Answer 1

Надо сесть и аккуратненько расписать варианты. Очевидно, что в силу неубывания ряда A,B,C,D проверять надо только условие x+y>z.

Допустим, у нас уже есть x и y. Тогда

C <= z <= x+y-1
C <= z <= D

Т.е. C <= z <= min(D,x+y-1), так что для данных x и y надо прибавить к результату min(D,x+y-1)-C+1 треугольников, если это число не меньше нуля :) Уже получили O(n^2), но этого все равно много...

Пусть есть x - каким может быть y? Здесь надо разбивать на части:

x+y-1 <= D

и

x+y-1 >= D+1

И опять расписывать минимумы, максимумы и две суммы.

"Оставим это читателю в качестве упражнения" (с) :)

Получившегося O(n) уже вполне достаточно, хотя, конечно, можно было бы поиграться и еще, но сложность уже начала бы зашкаливать.

Еще надо задуматься о том, что int'а может при перемножении таких чисел не хватить, так что лучше работать с long long.

Все это выливается в незатейливый код

int main(int argc, char * argv[])
{
    long long A, B, C, D;
    long long count = 0;
    cin >> A >> B >> C >> D;
    for(long long x = A; x <= B; ++x)
    {
        long long delta = 0;
        if (C >= max(B,D-x+2)) delta = (D-C+1)*(C - max(B,D-x+2) + 1);

        long long m = max(C-x,B), M = min(C, D+1-x);
        if (m <= M) delta += (2*x-2*C+m+M)*(M-m+1)/2;

        count += delta;
    }
    cout << count << endl;
}

который вполне проходит проверялку (которую вы зря прячете; легче работать, когда есть URL и можно предварительно проверить предлагаемое в качестве ответа на вопрос решение).

БЛОГ НА HUSL

Оптимизация задачи

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