@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;

Ошибка:5fe838848b335538235594.jpeg
  • Вопрос задан
  • 114 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@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, тогда ответ тупо количество всех пар.
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
iChar Санкт-Петербург
от 120 000 до 180 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
27 янв. 2021, в 00:37
11111 руб./за проект
26 янв. 2021, в 23:30
3000 руб./за проект
26 янв. 2021, в 23:07
1000 руб./за проект