Застрял в проблеме 8 проекта euler, получая неправильный ответ, но код кажется правильным

Question

#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;

int main(){
    int arr[1000] = {0} ;
    int k = 0 ;
    string s ;
    for (int i=0 ; i<20 ; i++){
        cin >> s ;
        for (int j=0 ; j<50 ; j++){
            arr[k] = (int)(s[j]-'0') ;
            k++ ;
        }
    }
    long long int product = 1 , maxi = 0 ;
    for (int i=0 ; i+12 < 1000 ; i++){
        product = arr[i]*arr[i+1]*arr[i+2]*arr[i+3]*arr[i+4]*arr[i+5]*arr[i+6]*arr[i+7]*arr[i+8]*arr[i+9]*arr[i+10]*arr[i+11]*arr[i+12] ; 
        if (maxi < product){
            maxi = product ;
        }
    }
    cout << maxi << endl ;
    return 0 ;
}

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

Answer 1

Вычисление product в вашем коде действительно должно быть сделано, используя al oop.

Вместо этого:

product = arr[i]*arr[i+1]*arr[i+2]*arr[i+3]*arr[i+4]*arr[i+5]*arr[i+6]*arr[i+7]*arr[i+8]*arr[i+9]*arr[i+10]*arr[i+11]*arr[i+12] ; 

попробуйте это:

for (product=arr[i], j=1; j<13; j++) product *= arr[i+j];

Мало того, что он намного короче и намного проще для чтения, обслуживания и отладки, но также позволит избежать ошибок целочисленного переполнения, из-за которых ваша программа давала неправильные ответы.

В C выражение, умножающее две int переменные (например, arr[i]*arr[i+1]), сгенерирует int результат. Если этот результат слишком велик, чтобы поместиться в переменную int (обычно ограниченную 2 ³¹ -1, что намного меньше, чем 9 ¹³ ), тогда он будет переполнен, и вы получит неправильный результат.

С другой стороны, если вы умножите переменную long long int на переменную int (как в product *= arr[i+j]), значение int будет повышено до long long int до выполнения расчета. Такое поведение называется «продвижение типа». Подробнее об этом можно прочитать здесь.

Answer 2

Ваши элементы массива имеют тип int, поэтому их умножение выполняется с использованием int - даже если результат присваивается long long int, что не влияет на вычисления. Это вызывает переполнение, потому что в худшем случае произведение из 13 цифр может достигать 13 ^ 9 = 2541865828329, что превышает INT_MAX, что, вероятно, 2 ^ 31 - 1. Возможно, с использованием long long int для типа массива, или приведите элементы к большему типу int перед умножением их.