В чем может быть ошибка?

Question

[iamrestik]

int n,a;
cin>>n>>a;
int count;
for(int j=1;j<=n;j++)
    for(int i=1;i<=j;i++)
        if(j-i<=a)count++;
cout<<count;

Ошибка:

Comments

[15432]

так а условие какое?

[iamrestik]

15432, Задание следующее. Cколько существует таких пар (i,  j), что 1 <= i  <= j  <= n, j - i <= a
В первой строке записаны два целых положительных числа n и a.
Нужно Вывести одно целое число - количество пар

[15432]

предположу, что вы не учли случаи, когда:
n = 0
n - отрицательное
n > MAXINT
count > MAXINT

[iamrestik]

15432, написал на питоне

n, a = map(int, input().split())

g2 = 0

for j in range(0, n + 1):
    for i in range(1, j + 1):
        if j - i <= a:
            g2 += 1

print(g2)

Ту же ошибку выдает,нужна оптимизация кода

[Александр]

он код "тупо скопировал" не прочитав условия, там у него задан диапазон для n и a был, который он не проверяет. А мне лень писать было эту херь.

[iamrestik]

Александр, Можете написать код целиком? Прерывается из-за тайм аута,видимо я код не правильно написал

[Александр]

Ну напиши сам хоть что-то, смысл вообще этим заниматься если только до cin>>n>>a; cout<<count;мозгов хватает.

[15432]

ну давайте оптимизировать. начнем с самого простого - отсекаем лишнее по второму циклу. нет смысла перебирать все i

for(int j=1;j<=n;j++)
    for(int i=j-a;i<=j;i++)
        if (i >=1)
            count++;

[15432]

Александр, не, там скорее как раз не требуется диапазон проверять, а дело в не оптимальности

[Александр]

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

[iamrestik]

15432, Решил,оказывается нужно через один цикл for,а я ебашил двумя

[Евгений Шатунов]

https://qna.habr.com/user/ggbet и https://qna.habr.com/user/iamrestik - это два аккаунта одного человека.
Данный вопрос был удален с профиля ggbet и опубликован повторно с профиля iamrestik. И пользователь сам этого не скрывает.
П6.5 регламента работы сервиса запрещает создание нескольких учетных записей.

[hint000]

iamrestik, там и один цикл нафиг не нужен.

если a>=n то count=n*(n+1)/2
если 0<=a<n то count=(a+1)*n-a*(a+1)/2
если 0>a то count=0

Всё. Циклы не нужны.

[Александр]

вот, сразу видно кто с мозгами

Answer 1

[Wataru]

Ошибка в том, что ваш наивный алгоритм слишком медленный.

Посидите с бумажкой, тут вообще можно формулу для ответа вывести.
Подсказка: сколько существует i<=j, таких что j-i <= a? Перобразуйте второе неравенство, получите i >= j-a.
В итоге у вас есть неравенства j-a <= i <= j. Если j >= a+1, то ровно a+1 чисел в этом интервале. Иначе их там j, (потому что левая граница отрицательна или 0, а по условию i >= 1).

Итого ваш ответ - это сумма от 1 до a, а потом еще n-a слагаемых a. Сумма первой части - арифметическая прогрессия.

Надо только не забыть рассмотреть случай a>=n-1, тогда ответ тупо количество всех пар.