AtCoder題解——Beginner Contest 169——B - Multiplication 2

題目相關

題目連結

AtCoder Beginner Contest 169 B題，https://atcoder.jp/contests/abc169/tasks/abc169_b。

Problem Statement

Given N integers A1,...,AN compute A1×...×AN.

However, if the result exceeds 10^18, print 

-1

 instead.

Input

Input is given from Standard Input in the following format:

N
A1 ... An
           

Output

Print the value A1×...×AN as an integer, or 

-1

 if the value exceeds 10^18.

Samples1

Sample Input 1

2
1000000000 1000000000
           

Sample Output 1

1000000000000000000
           

Explaination

We have 1000000000×1000000000=1000000000000000000.

Samples2

Sample Input 2

3
101 9901 999999000001
           

Sample Output 2

-1
           

Explaination

We have  101×9901×999999000001=1000000000000000001, which exceeds 10^18, so we should print 

-1

 instead.

Samples3

Sample Input 3

31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0
           

Sample Output 3

Constraints

• 2 ≤ N ≤ 10^5
• 0 ≤ Ai ≤10^18
• All values in input are integers.

題解報告

本題含義

給了 N 個數，要求我們計算這 N 個數的乘積。但是這個乘積有個限制，如果乘積超過 10^18 這個數，我們就要輸出 -1。

樣例資料分析

本題的難度不大。樣例資料 1 和樣例資料 2 沒有什麼需要分析的地方。我們要重點觀察一下樣例資料 3。

我們不難發現 

 已經超過了 10^18。但是題目給出的參考答案是 0。

也就是說，本樣例資料是一個卡人的地方。就是說如果輸入資料中有 0 存在，不管如何乘積的結果都不會超過 10^18。

是以本題不能直接讀入資料累乘進行判斷。

本題的難點

我們知道在 C++ 中，unsigned long long 的最大值是 2^64-1，也就是1.84*10^19。是以本題的難點在于如何判斷兩個數乘積超過了 unsigned long long 的範圍，也就是資料越界。

判斷兩個數乘積是否超過資料的表示範圍，我們可以用除法。假設兩個數分别為 a 和 b，我們隻需要用：最大值 / a 和 b 進行比較即可。如果 最大值 / a 小于 b，說明越界；否則不越界。

這個我們可以非常輕松的用一個簡單數字來說明。如果 a 和 b 都是正數，而且 a*b 的值不能超過 10。那麼當 a = 5 的時候，b 的取值範圍隻能是：0、1、2，這三個數。是以 10/5=2。

解決了這個判斷，本題就很容易了。

算法設計

1、讀入 N 個資料。如果資料中有零，直接輸出答案。

2、從第一個資料開始累乘，判斷乘積是否會超過 unsigned long long 的表示範圍或者超過 10^18。

AC 參考代碼

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

const int MAXN = 2e5+2;
unsigned long long nums[MAXN];

const long long MAXL = 1e18;

//判斷a*b是否超過1e18
bool overflow(unsigned long long a, unsigned long long b) {
    //判斷是否越界
    if (ULLONG_MAX / a < b) {
        return true;
    }
    //判斷是否超過1e18
    unsigned long long ans = a*b;
    if (ans>MAXL) {
        return true;
    }
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%llu", &nums[i]);
        if (0==nums[i]) {
            printf("0\n");
            return 0;
        }
    }

    long long ans=1;
    for (int i=0; i<n; i++) {
        if (true == overflow(ans, nums[i])) {
            printf("-1\n");
            return 0;
        }
        ans *= nums[i];
    }

    printf("%llu", ans);

    return 0;
}