@Homemade

Как побороть переполнение?

Решаю задачу.
Мой
код
#include <bits/stdc++.h>

using namespace std;

long long div_up(int x, int y)
{
    return (x - 1) / y + 1;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        long long n,x;
        cin>>n>>x;
        vector<int> a(n);
        for(int i=0;i<n;i++)
            cin>>a[i];
        long long sum = 0;
        for(int i=0;i<n;i++)
            sum = sum + a[i];

        long long sum2 = 0;
        for(int i=0;i<n;i++)
            sum2 = sum2 + div_up(a[i],x);

        long long mn = div_up(sum,x),mx = sum2;

        cout<<mn<<" "<<mx<<endl;
    }
    return 0;
}

На большом числе выдало ошибку:

Ввод
1
100000 501901246
856802259 964126361 36942580 586287303 899177135 447296776 ...
Вывод
2 149973
Ответ
99678 149973
Протокол тестирования
wrong answer 1st numbers differ - expected: '99678', found: '2'

Думаю дело в переполнении переменной sum, но не знаю как быть.
  • Вопрос задан
  • 121 просмотр
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Проанализировать, как меняется красота при операции сложения элементов и работать с остатками от деления.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
В этой задаче все должно в long long помещаться. Никаких трюков не надо.

У вас ошибка вот тут:
long long div_up(int x, int y)

Типа параметров - int. Вы когда в эту функцию передаете long long сумму - происходит переполнение.

Просто измените типы на long long и должно пройти.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

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

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