AtCoder Beginner Contest

【pythonでABC169を解説】B - Multiplication 2

問題概要

問題ページ

問題文

\(N\) 個の整数 \(A_1,...,A_N\) が与えられます。

\(A_1 \times ... \times A_N\) を求めてください。

ただし、結果が \(10^{18}\) を超える場合は、代わりに -1 を出力してください。

制約

  • \(2 \leq N \leq 10^5\)
  • \(0 \leq A_i \leq 10^{18}\)
  • 入力は全て整数である。

問題の考察

問題はシンプルで各\(A_i\)の総乗(全てを掛け算する)を求めれば良い。

「\(10^18\)を超える場合には-1を出力する」とあるが、掛け算の性質を忘れると間違ってしまう。

\(1 \times 2 \times ... \times 100 \times 0\)

のように最後が\(0\)の場合、全て計算すると答えは\(0\)になるが途中で\(10 ^ 18\)を超えてしまい-1を出力してしまう。

全て計算しようとしても\(10^18\)が\(10^5\)個だと計算が間に合わずにTLEしてしまう。

\(A_1,...,A_N\)をsort()で昇順に並び替えてから計算する必要がある。

\(0 \leq A_i \leq 10^{18}\)なので、負の値は存在しないので間に合う。

負の値がある場合でも\(0\)をカウントして処理すれば計算できる。

昇順に並び替える場合

  • sort()で昇順に並び替える
  • 総乗が\(0\)になったら0を出力
  • \(10^18\)を超えたら-1を出力
  • それ以外の場合には計算した総乗を出力

0をカウントする場合

  • \(0\)をカウントして存在すれば\(0\)を出力
  • 存在ければ順に計算し\(10^18\)を超えたら-1を出力
  • それ以外の場合には計算した総乗を出力

ACコードは昇順に並び替える方法で解答しています。

たびすけ
問題文は難しくないけど油断すると間違えてしまう問題!

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    a.sort()
    t = 1
    limit = pow(10, 18)
    for i in range(n):
        t *= a[i]
        if t > limit:
            print(-1)
            exit()
    print(t)


if __name__ == '__main__':
    solve()

-AtCoder Beginner Contest
-